Recognizable colorings of cycles and trees
Michael J. Dorfling, Samantha Dorfling · Discussiones Mathematicae Graph Theory · 2012
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 0 , a 1 , . . ., a k ), where a 0 = 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.