A checkerboard problem and modular colorings of graphs
Ebrahim Salehi, Futaba Okamoto, P. Zhang · 2010
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. The modular chromatic numbers of several well-known graphs are determined and a number of bounds are presented. For every nontrivial tree T , it is shown that mc(T ) = 2 or mc(T ) = 3. For every integer r ≥ 3, it is shown that there exists an r-chromatic graph G with mc(G) = r + 1. Several open problems are presented, including whether the modular chromatic number of every grid is 2, which has a checkerboard interpretation. Another open problem is whether there exists a planar graph with modular chromatic number 5.