Coloring Grids Avoiding Bicolored Paths
arXiv:2312.12919
The paper determines that at least four colors are required to properly color a rectangular grid (the Cartesian product of two paths) while avoiding any bicolored path of a given length, except when the grid dimensions are too small for such a path.
Abstract
The star chromatic number on a graph is the minimum number of colors in a proper vertex coloring forbidding any with two colors (bicolored). This problem was introduced by Grünbaum (1973) together with the acyclic coloring of graphs, where bicolored cycles are avoided. In this paper, we study a generalization of this problem, by considering proper vertex coloring on graphs forbidding bicolored paths of a fixed length, which was initially discussed by Alon, McDiarmid, and Reed (1991). Here, we study this problem on products of two paths. We show that at least 4 colors are needed to properly color the product of paths, , avoiding a bicolored unless or With this result, the above question is settled for all on 2-dimensional grids.