# Recognizable colorings of graphs

Gary Chartrand; Linda Lesniak; Donald W. VanderJagt; Ping Zhang

Discussiones Mathematicae Graph Theory (2008)

- Volume: 28, Issue: 1, page 35-57
- ISSN: 2083-5892

## Access Full Article

top## Abstract

top## How to cite

topGary Chartrand, et al. "Recognizable colorings of graphs." Discussiones Mathematicae Graph Theory 28.1 (2008): 35-57. <http://eudml.org/doc/270473>.

@article{GaryChartrand2008,

abstract = {Let G be a connected graph and let c:V(G) → 1,2,...,k be a coloring of the vertices of G for some positive integer k (where adjacent vertices may be colored the same). The color code of a vertex v of G (with respect to c) is the ordered (k+1)-tuple code(v) = (a₀,a₁,...,aₖ) where a₀ is the color assigned to v and for 1 ≤ i ≤ k, $a_i$ is the number of vertices adjacent to v that are colored i. The coloring c is called recognizable if distinct vertices have distinct color codes and the recognition number rn(G) of G is the minimum positive integer k for which G has a recognizable k-coloring. Recognition numbers of complete multipartite graphs are determined and characterizations of connected graphs of order n having recognition numbers n or n-1 are established. It is shown that for each pair k,n of integers with 2 ≤ k ≤ n, there exists a connected graph of order n having recognition number k. Recognition numbers of cycles, paths, and trees are investigated.},

author = {Gary Chartrand, Linda Lesniak, Donald W. VanderJagt, Ping Zhang},

journal = {Discussiones Mathematicae Graph Theory},

keywords = {recognizable coloring; recognition number},

language = {eng},

number = {1},

pages = {35-57},

title = {Recognizable colorings of graphs},

url = {http://eudml.org/doc/270473},

volume = {28},

year = {2008},

}

TY - JOUR

AU - Gary Chartrand

AU - Linda Lesniak

AU - Donald W. VanderJagt

AU - Ping Zhang

TI - Recognizable colorings of graphs

JO - Discussiones Mathematicae Graph Theory

PY - 2008

VL - 28

IS - 1

SP - 35

EP - 57

AB - Let G be a connected graph and let c:V(G) → 1,2,...,k be a coloring of the vertices of G for some positive integer k (where adjacent vertices may be colored the same). The color code of a vertex v of G (with respect to c) is the ordered (k+1)-tuple code(v) = (a₀,a₁,...,aₖ) where a₀ is the color assigned to v and for 1 ≤ i ≤ k, $a_i$ is the number of vertices adjacent to v that are colored i. The coloring c is called recognizable if distinct vertices have distinct color codes and the recognition number rn(G) of G is the minimum positive integer k for which G has a recognizable k-coloring. Recognition numbers of complete multipartite graphs are determined and characterizations of connected graphs of order n having recognition numbers n or n-1 are established. It is shown that for each pair k,n of integers with 2 ≤ k ≤ n, there exists a connected graph of order n having recognition number k. Recognition numbers of cycles, paths, and trees are investigated.

LA - eng

KW - recognizable coloring; recognition number

UR - http://eudml.org/doc/270473

ER -

## References

top- [1] L. Addario-Berry, R.E.L. Aldred, K. Dalal and B.A. Reed, Vertex colouring edge partitions, J. Combin. Theory (B) 94 (2005) 237-244, doi: 10.1016/j.jctb.2005.01.001. Zbl1074.05031
- [2] M. Aigner and E. Triesch, Irregular assignments and two problems á la Ringel, in: Topics in Combinatorics and Graph Theory, R. Bodendiek and R. Henn, eds. (Physica, Heidelberg, 1990) 29-36.
- [3] M. Aigner, E. Triesch and Z. Tuza, Irregular assignments and vertex-distinguishing edge-colorings of graphs, Combinatorics' 90 (Elsevier Science Pub., New York, 1992) 1-9.
- [4] P.N. Balister, E. Gyori, J. Lehel and R.H. Schelp, Adjacent vertex distinguishing edge-colorings, SIAM J. Discrete Math. 21 (2007) 237-250, doi: 10.1137/S0895480102414107. Zbl1189.05056
- [5] A.C. Burris, On graphs with irregular coloring number 2, Congr. Numer. 100 (1994) 129-140 Zbl0836.05029
- [6] A.C. Burris, The irregular coloring number of a tree, Discrete Math. 141 (1995) 279-283, doi: 10.1016/0012-365X(93)E0225-S. Zbl0829.05027
- [7] G. Chartrand, H. Escuadro, F. Okamoto and P. Zhang, Detectable colorings of graphs, Util. Math. 69 (2006) 13-32. Zbl1102.05020
- [8] G. Chartrand, M.S. Jacobson, J. Lehel, O.R. Oellermann, S. Ruiz and F. Saba, Irregular networks, Congress. Numer. 64 (1988) 197-210.
- [9] G. Chartrand and L. Lesniak, Graphs & Digraphs: Fourth Edition (Chapman & Hall/CRC, Boca Raton, FL, 2005).
- [10] H. Escuadro, F. Okamoto and P. Zhang, A three-color problem in graph theory, Bull. Inst. Combin. Appl., to appear. Zbl1146.05022
- [11] F. Harary and M. Plantholt, The point-distinguishing chromatic index, in: Graphs and Applications (Wiley, New York, 1985) 147-162. Zbl0562.05023
- [12] M. Karoński, T. Łuczak and A. Thomason, Edge weights and vertex colours, J. Combin. Theory (B) 91 (2004) 151-157, doi: 10.1016/j.jctb.2003.12.001. Zbl1042.05045

## Citations in EuDML Documents

top- Michael J. Dorfling, Samantha Dorfling, Recognizable colorings of cycles and trees
- Gary Chartrand, Futaba Okamoto, Ebrahim Salehi, Ping Zhang, The multiset chromatic number of a graph
- Futaba Okamoto, Ebrahim Salehi, Ping Zhang, On multiset colorings of graphs
- Futaba Okamoto, Bryan Phinezy, Ping Zhang, The local metric dimension of a graph
- Yun Feng, Wensong Lin, On multiset colorings of generalized corona graphs

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.