PDF

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

RECOGNIZABLE COLORINGS OF GRAPHS

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)

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_k) 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.

Keywords: recognizable coloring, recognition number.

2000 Mathematics Subject Classification: 05C15, 05C70.

References

[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