On Closed Modular Colorings of Trees

Bryan Phinezy ; Ping Zhang

Discussiones Mathematicae Graph Theory, Tome 33 (2013) no. 2, p. 411.

Résumé

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.

Détail

Classification : 05C05, 05C15
Mots-clés : trees, closed modular k-coloring, closed modular chromatic number, closed modular -colouring