Brooks-type theorems for relaxations of square colorings

Abstract

The following relaxation of proper coloring the square of a graph was recently introduced: for a positive integer h, the proper h-conflict-free chromatic number of a graph G, denoted χpcfh(G), is the minimum k such that G has a proper k-coloring where every vertex v has min⁡{degG⁡(v),h} colors appearing exactly once on its neighborhood. Caro, Petruševski, and Škrekovski put forth a Brooks-type conjecture: if G is a graph with Δ(G)≥3, then χpcf1(G)≤Δ(G)+1. The best known result regarding the conjecture is χpcf1(G)≤2Δ(G)+1, which is implied by a result of Pach and Tardos. We improve upon the aforementioned result for all h, and also enlarge the class of graphs for which the conjecture is known to be true. Our main result is the following: for a graph G, if Δ(G)≥h+2, then χpcfh(G)≤(h+1)Δ(G)−1; this is tight up to the additive term as we explicitly construct infinitely many graphs G with χpcfh(G)=(h+1)(Δ(G)−1). We also show that the conjecture is true for chordal graphs, and obtain partial results for quasi-line graphs and claw-free graphs. Our main result also improves upon a Brooks-type result for h-dynamic coloring.