PDF
Discussiones Mathematicae Graph Theory 33(2) (2013)
411-428
DOI: https://doi.org/10.7151/dmgt.1678
On Closed Modular Colorings of Trees
| Bryan Phinezy and Ping Zhang
Department of Mathematics |
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) → ℤk be a vertex coloring where adjacent vertices may be assigned the same color. The coloring c induces another vertex coloring c ′: V(G) → ℤk defined by c ′(v) = ∑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) ≠ c ′(v) in ℤk 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) ≠ 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.
Keywords: trees, closed modular k-coloring, closed modular chromatic number
2010 Mathematics Subject Classification: 05C05, 05C15.
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] | G. Chartrand, M.S. Jacobson, J. Lehel, O.R. Oellermann, S. Ruiz and F. Saba, Irregular networks, Congr. Numer. 64 (1988) 197--210. |
| [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. |
| [4] | G. Chartrand, B. Phinezy and P. Zhang, On closed modular colorings of regular graphs, Bull. Inst. Combin. Appl. 66 (2012) 7--32. |
| [5] | G. Chartrand, L. Lesniak and P. Zhang, Graphs & Digraphs, 5th Edition (Chapman & Hall/CRC, Boca Raton, 2010). |
| [6] | G. Chartrand and P. Zhang, Chromatic Graph Theory (Chapman & Hall/CRC, Boca Raton, 2008). |
| [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. |
| [8] | J.A. Gallian, A dynamic survey of graph labeling, Electron. J. Combin. 16 (2009) #DS6. |
| [9] | R.B. Gnana Jothi, Topics in Graph Theory, Ph.D. Thesis, Madurai Kamaraj University 1991. |
| [10] | S.W. Golomb, How to number a graph, in: Graph Theory and Computing (Academic Press, New York, 1972) 23--37. |
| [11] | R. Jones, K. Kolasinski and P. Zhang, A proof of the modular edge-graceful trees conjecture, J. Combin. Math. Combin. Comput., to appear. |
| [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. |
| [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. |
Received 11 January 2012
Accepted 11 June 2012
Close