Discussiones Mathematicae Graph Theory 28(1) (2008) 35-57
doi: 10.7151/dmgt.1390

[BIBTex] [PDF] [PS]


Gary Chartrand

Department of Mathematics
Western Michigan University
Kalamazoo, MI 49008, USA

Linda Lesniak

Department of Mathematics
and Computer Science, Drew University
Madison, NJ 07940, USA

Donald W. VanderJagt

Department of Mathematics
Grand Valley State University
Allendale, MI 49401, USA

Ping Zhang

Department of Mathematics
Western Michigan University
Kalamazoo, MI 49008, USA

Dedicated to the memory of Frank Harary (1921-2005)


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) = (a0,a1,☐,ak) where a0 is the color assigned to v and for 1 ≤ i ≤ k, ai 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.

Keywords: recognizable coloring, recognition number.

2000 Mathematics Subject Classification: 05C15, 05C70.


[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.
[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.
[5] A.C. Burris, On graphs with irregular coloring number 2, Congr. Numer. 100 (1994) 129-140
[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.
[7] G. Chartrand, H. Escuadro, F. Okamoto and P. Zhang, Detectable colorings of graphs, Util. Math. 69 (2006) 13-32.
[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.
[11] F. Harary and M. Plantholt, The point-distinguishing chromatic index, in: Graphs and Applications (Wiley, New York, 1985) 147-162.
[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.

Received 12 June 2006
Accepted 30 October 2007