Coloring Grids Avoiding Bicolored Paths
This solves a specific combinatorial graph coloring problem for 2-dimensional grids, which is incremental to prior work on bicolored path avoidance.
The paper addresses the problem of properly coloring grid graphs (products of two paths) while avoiding bicolored paths of a fixed length, showing that at least 4 colors are needed unless the grid dimensions are smaller than the path length minus 2.
The star chromatic number on a graph is the minimum number of colors in a proper vertex coloring forbidding any $P_4$ 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, $P_m\square P_n$, avoiding a bicolored $P_k,$ unless $n<k-2$ or $m<k-2.$ With this result, the above question is settled for all $k$ on 2-dimensional grids.