Coloring of Graphs Avoiding Bicolored Paths of a Fixed Length

The problem of finding the minimum number of colors to color a graph properly without containing any bicolored copy of a fixed family of subgraphs has been widely studied. Most well-known examples are star coloring and acyclic coloring of graphs (Grünbaum, 1973) where bicolored copies of P₄ and cycles are not allowed, respectively. We introduce a variation of these problems and study proper coloring of graphs not containing a bicolored path of a fixed length and provide general bounds for all graphs. A P_k -coloring of an undirected graph G is a proper vertex coloring of G such that there is no bicolored copy of P_k in G, and the minimum number of colors needed for a P_k -coloring of G is called the P_k -chromatic number of G, denoted by s_k(G). We provide bounds on s_k(G) for all graphs, in particular, proving that for any graph G with maximum degree d≥ 2, and k≥ 4, sk(G)≤⌈610dk-1k-2⌉. Moreover, we find the exact values for the P_k -chromatic number of the products of some cycles and paths for k= 5, 6.