Proper Conflict-Free Coloring of Graphs with Large Maximum Degree
Daniel W. Cranston, Chun‐Hung Liu · SIAM Journal on Discrete Mathematics · 2024
Abstract. A proper coloring of a graph is conflict-free if, for every nonisolated vertex, some color is used exactly once on its neighborhood. Caro, Petruševski, and Škrekovski [ Discrete Math., 346 (2023), 113221] proved that every graph [Formula: see text] has a proper conflict-free coloring with at most [Formula: see text] colors and conjectured that [Formula: see text] colors suffice for every connected graph [Formula: see text] with [Formula: see text]. Our first main result is that even for list-coloring, [Formula: see text] colors suffice for every graph [Formula: see text] with [Formula: see text]; we also prove slightly weaker bounds for all graphs with [Formula: see text]. These results follow from our more general framework on proper conflict-free list-coloring of a pair consisting of a graph [Formula: see text] and a “conflict” hypergraph [Formula: see text]. As another corollary of our results in this general framework, every graph has a proper [Formula: see text]-list-coloring such that every bichromatic 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 [Formula: see text] has a fractional [Formula: see text]-coloring such that every fractionally bichromatic component has at most two vertices. In particular, it implies that the fractional analogue of the conjecture of Caro, Petruševski, and Škrekovski holds asymptotically in a strong sense.