DMGT

Discussiones Mathematicae Graph Theory 32(1) (2012) 81-90
DOI: https://doi.org/10.7151/dmgt.1587

Recognizable Colorings of Cycles and Trees

Michael J. Dorfling

Department of Mathematics
University of Johannesburg
Johannesburg, South Africa

Samantha Dorfling

Department of Mathematics and Applied Mathematics
University of the Free State
Bloemfontein, South Africa

Abstract

For a graph G and a vertex-coloring c:V(G)→{1,2, …,k}, the color code of a vertex v is the (k+1)-tuple (a₀,a₁, …,a_k), where a₀ = c(v), and for 1 ≤ i ≤ k, a_i is the number of neighbors of v colored i. A recognizable coloring is a coloring such that distinct vertices have distinct color codes. The recognition number of a graph is the minimum k for which G has a recognizable k-coloring. In this paper we prove three conjectures of Chartrand et al. in [8] regarding the recognition number of cycles and trees.

Keywords: recognizable coloring, recognition number

2010 Mathematics Subject Classification: 05C15, 05C70.

References

[1]	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.
[2]	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.
[3]	A.C. Burris, On graphs with irregular coloring number 2, Congr. Numer. 100 (1994) 129--140.
[4]	A.C. Burris, The irregular coloring number of a tree, Discrete Math. 141 (1995) 279--283, doi: 10.1016/0012-365X(93)E0225-S.
[5]	G. Chartrand, H. Escuadro, F. Okamoto and P. Zhang, Detectable colorings of graphs, Util. Math. 69 (2006) 13--32.
[6]	G. Chartrand, M.S. Jacobson, J. Lehel, O.R. Oellermann, S. Ruiz and F. Saba, Irregular networks, Congress. Numer. 64 (1988) 197--210.
[7]	G. Chartrand and L. Lesniak, Graphs & Digraphs: Fourth Edition (Chapman & Hall/CRC, Boca Raton, FL, 2005).
[8]	G. Chartrand, L. Lesniak, D.W. VanderJagt and P. Zhang, Recognizable colorings of graphs, Discuss. Math. Graph Theory 28 (2008) 35--57, doi: 10.7151/dmgt.1390.
[9]	F. Harary and M. Plantholt, The point-distinguishing chromatic index, in: Graphs and Applications (Wiley, New York, 1985) 147--162.

Received 16 July 2010
Revised 25 January 2011
Accepted 25 January 2011