On Closed Modular Colorings of Trees

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 -