Proper Conflict-free Coloring of Graphs with Large Maximum Degree
arXiv:2211.02818 · doi:10.1137/23M1563281
Abstract
A proper coloring of a graph is \emph{conflict-free} if, for every non-isolated vertex, some color is used exactly once on its neighborhood. Caro, Petruševski, and Škrekovski proved that every graph has a proper conflict-free coloring with at most colors and conjectured that colors suffice for every connected graph with . Our first main result is that even for list-coloring, colors suffice for every graph with ; we also prove slightly weaker bounds for all graphs with . These results follow from our more general framework on proper conflict-free list-coloring of a pair consisting of a graph and a "conflict" hypergraph . As another corollary of our results in this general framework, every graph has a proper -list-coloring such that every bi-chromatic component is a path on at most three vertices, where the number of colors is optimal up to a constant factor. Our proof uses a fairly new type of recursive counting argument called Rosenfeld counting, which is a variant of the Lovász Local Lemma or entropy compression. We also prove an asymptotically optimal result for a fractional analogue of our general framework for proper conflict-free coloring for pairs of a graph and a conflict hypergraph. A corollary states that every graph has a fractional -coloring such that every fractionally bi-chromatic component has at most two vertices. In particular, it implies that the fractional analogue of the conjecture of Caro et al.\ holds asymptotically in a strong sense.