# Recognizable colorings of cycles and trees

Michael J. Dorfling; Samantha Dorfling

Discussiones Mathematicae Graph Theory (2012)

- Volume: 32, Issue: 1, page 81-90
- ISSN: 2083-5892

## Access Full Article

top## Abstract

top## How to cite

topMichael J. Dorfling, and Samantha Dorfling. "Recognizable colorings of cycles and trees." Discussiones Mathematicae Graph Theory 32.1 (2012): 81-90. <http://eudml.org/doc/271084>.

@article{MichaelJ2012,

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ₖ), 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.},

author = {Michael J. Dorfling, Samantha Dorfling},

journal = {Discussiones Mathematicae Graph Theory},

keywords = {recognizable coloring; recognition number},

language = {eng},

number = {1},

pages = {81-90},

title = {Recognizable colorings of cycles and trees},

url = {http://eudml.org/doc/271084},

volume = {32},

year = {2012},

}

TY - JOUR

AU - Michael J. Dorfling

AU - Samantha Dorfling

TI - Recognizable colorings of cycles and trees

JO - Discussiones Mathematicae Graph Theory

PY - 2012

VL - 32

IS - 1

SP - 81

EP - 90

AB - 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ₖ), 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.

LA - eng

KW - recognizable coloring; recognition number

UR - http://eudml.org/doc/271084

ER -

## References

top- [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. Zbl0836.05029
- [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. Zbl0829.05027
- [5] G. Chartrand, H. Escuadro, F. Okamoto and P. Zhang, Detectable colorings of graphs, Util. Math. 69 (2006) 13-32. Zbl1102.05020
- [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. Zbl1235.05049
- [9] F. Harary and M. Plantholt, The point-distinguishing chromatic index, in: Graphs and Applications (Wiley, New York, 1985) 147-162. Zbl0562.05023

## NotesEmbed ?

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