# On Closed Modular Colorings of Trees

• Volume: 33, Issue: 2, page 411-428
• ISSN: 2083-5892

top

## Abstract

top
Two vertices u and v in a nontrivial connected graph G are twins if u and v have the same neighbors in V (G) − {u, v}. If u and v are adjacent, they are referred to as true twins; while if u and v are nonadjacent, they are false twins. For a positive integer k, let c : V (G) → Zk be a vertex coloring where adjacent vertices may be assigned the same color. The coloring c induces another vertex coloring c′ : V (G) → Zk defined by c′(v) = P u∈N[v] c(u) for each v ∈ V (G), where N[v] is the closed neighborhood of v. Then c is called a closed modular k-coloring if c′(u) 6= c′(v) in Zk for all pairs u, v of adjacent vertices that are not true twins. The minimum k for which G has a closed modular k-coloring is the closed modular chromatic number mc(G) of G. The closed modular chromatic number is investigated for trees and determined for several classes of trees. For each tree T in these classes, it is shown that mc(T) = 2 or mc(T) = 3. A closed modular k-coloring c of a tree T is called nowhere-zero if c(x) 6= 0 for each vertex x of T. It is shown that every tree of order 3 or more has a nowhere-zero closed modular 4-coloring.

## How to cite

top

Bryan Phinezy, and Ping Zhang. "On Closed Modular Colorings of Trees." Discussiones Mathematicae Graph Theory 33.2 (2013): 411-428. <http://eudml.org/doc/267972>.

@article{BryanPhinezy2013,
abstract = {Two vertices u and v in a nontrivial connected graph G are twins if u and v have the same neighbors in V (G) − \{u, v\}. If u and v are adjacent, they are referred to as true twins; while if u and v are nonadjacent, they are false twins. For a positive integer k, let c : V (G) → Zk be a vertex coloring where adjacent vertices may be assigned the same color. The coloring c induces another vertex coloring c′ : V (G) → Zk defined by c′(v) = P u∈N[v] c(u) for each v ∈ V (G), where N[v] is the closed neighborhood of v. Then c is called a closed modular k-coloring if c′(u) 6= c′(v) in Zk for all pairs u, v of adjacent vertices that are not true twins. The minimum k for which G has a closed modular k-coloring is the closed modular chromatic number mc(G) of G. The closed modular chromatic number is investigated for trees and determined for several classes of trees. For each tree T in these classes, it is shown that mc(T) = 2 or mc(T) = 3. A closed modular k-coloring c of a tree T is called nowhere-zero if c(x) 6= 0 for each vertex x of T. It is shown that every tree of order 3 or more has a nowhere-zero closed modular 4-coloring.},
author = {Bryan Phinezy, Ping Zhang},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {trees; closed modular k-coloring; closed modular chromatic number; closed modular -colouring},
language = {eng},
number = {2},
pages = {411-428},
title = {On Closed Modular Colorings of Trees},
url = {http://eudml.org/doc/267972},
volume = {33},
year = {2013},
}

TY - JOUR
AU - Bryan Phinezy
AU - Ping Zhang
TI - On Closed Modular Colorings of Trees
JO - Discussiones Mathematicae Graph Theory
PY - 2013
VL - 33
IS - 2
SP - 411
EP - 428
AB - Two vertices u and v in a nontrivial connected graph G are twins if u and v have the same neighbors in V (G) − {u, v}. If u and v are adjacent, they are referred to as true twins; while if u and v are nonadjacent, they are false twins. For a positive integer k, let c : V (G) → Zk be a vertex coloring where adjacent vertices may be assigned the same color. The coloring c induces another vertex coloring c′ : V (G) → Zk defined by c′(v) = P u∈N[v] c(u) for each v ∈ V (G), where N[v] is the closed neighborhood of v. Then c is called a closed modular k-coloring if c′(u) 6= c′(v) in Zk for all pairs u, v of adjacent vertices that are not true twins. The minimum k for which G has a closed modular k-coloring is the closed modular chromatic number mc(G) of G. The closed modular chromatic number is investigated for trees and determined for several classes of trees. For each tree T in these classes, it is shown that mc(T) = 2 or mc(T) = 3. A closed modular k-coloring c of a tree T is called nowhere-zero if c(x) 6= 0 for each vertex x of T. It is shown that every tree of order 3 or more has a nowhere-zero closed modular 4-coloring.
LA - eng
KW - trees; closed modular k-coloring; closed modular chromatic number; closed modular -colouring
UR - http://eudml.org/doc/267972
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[Crossref] Zbl1074.05031
2. [2] G. Chartrand, M.S. Jacobson, J. Lehel, O.R. Oellermann, S. Ruiz and F. Saba, Irregular networks, Congr. Numer. 64 (1988) 197-210.
3. [3] G. Chartrand, F. Okamoto and P. Zhang, The sigma chromatic number of a graph, Graphs Combin. 26 (2010) 755-773. doi:10.1007/s00373-010-0952-7[Crossref] Zbl1207.05049
4. [4] G. Chartrand, B. Phinezy and P. Zhang, On closed modular colorings of regular graphs, Bull. Inst. Combin. Appl. 66 (2012) 7-32. Zbl1332.05051
5. [5] G. Chartrand, L. Lesniak and P. Zhang, Graphs & Digraphs, 5th Edition (Chapman & Hall/CRC, Boca Raton, 2010).
6. [6] G. Chartrand and P. Zhang, Chromatic Graph Theory (Chapman & Hall/CRC, Boca Raton, 2008). doi:10.1201/9781584888017[Crossref]
7. [7] H. Escuadro, F. Okamoto and P. Zhang, Vertex-distinguishing colorings of graphs- A survey of recent developments, AKCE Int. J. Graphs Comb. 4 (2007) 277-299. Zbl1143.05305
8. [8] J.A. Gallian, A dynamic survey of graph labeling, Electron. J. Combin. 16 (2009) #.DS6 Zbl0953.05067
9. [9] R.B. Gnana Jothi, Topics in Graph Theory, Ph.D. Thesis, Madurai Kamaraj University 1991.
10. [10] S.W. Golomb, How to number a graph, in: Graph Theory and Computing (Academic Press, New York, 1972) 23-37.
11. [11] R. Jones, K. Kolasinski and P. Zhang, A proof of the modular edge-graceful trees conjecture, J. Combin. Math. Combin. Comput., to appear. Zbl1247.05207
12. [12] M. Karónski, T. Luczak and A. Thomason, Edge weights and vertex colours, J. Combin. Theory (B) 91 (2004) 151-157. doi:10.1016/j.jctb.2003.12.001[Crossref] Zbl1042.05045
13. [13] A. Rosa, On certain valuations of the vertices of a graph, in: Theory of Graphs, Pro. Internat. Sympos. Rome 1966 (Gordon and Breach, New York, 1967) 349-355.

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