On modular colorings of caterpillars
Ebrahim Salehi, Futaba Okamoto, P. Zhang · 2009
A modular k-coloring, k ≥ 2, of a graph G without isolated vertices is a coloring of the vertices of G with the elements in Zk (where adjacent vertices may be colored the same) having the property that for every two adjacent vertices of G, the sums of the colors of their neighbors are different in Zk. The minimum k for which G has a modular k-coloring is the modular chromatic number mc(G) of G. The modular chromatic number of a graph is at least as large as its chromatic number. It was known that if T is a nontrivial tree, then mc(T ) = 2 or mc(T ) = 3. A nontrivial tree T is of type one if mc(T ) = 2 and is of type two if mc(T ) = 3. It is shown that all nontrivial trees of diameter at most 6 are of type one. A caterpillar is a tree of order 3 or more, the removal of whose end-vertices produces a path. A characterization has been established for all caterpillars that are of type two.