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

Abstract

top
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.

How to cite

top

Gary 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. [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. [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. [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. [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. [5] A.C. Burris, On graphs with irregular coloring number 2, Congr. Numer. 100 (1994) 129-140 Zbl0836.05029
  6. [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. [7] G. Chartrand, H. Escuadro, F. Okamoto and P. Zhang, Detectable colorings of graphs, Util. Math. 69 (2006) 13-32. Zbl1102.05020
  8. [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. [9] G. Chartrand and L. Lesniak, Graphs & Digraphs: Fourth Edition (Chapman & Hall/CRC, Boca Raton, FL, 2005). 
  10. [10] H. Escuadro, F. Okamoto and P. Zhang, A three-color problem in graph theory, Bull. Inst. Combin. Appl., to appear. Zbl1146.05022
  11. [11] F. Harary and M. Plantholt, The point-distinguishing chromatic index, in: Graphs and Applications (Wiley, New York, 1985) 147-162. Zbl0562.05023
  12. [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

NotesEmbed ?

top

You must be logged in to post comments.

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.