Proper Conflict-free Coloring of Graphs with Large Maximum Degree

arXiv2211.02818MaRDI QIDQ6506972FDOQ6506972

Chun-Hung Liu, Daniel W. Cranston

Abstract: A proper coloring of a graph is conflict-free if, for every non-isolated vertex, some color is used exactly once on its neighborhood. Caro, Petruv{s}evski, and v{S}krekovski proved that every graph $G$ has a proper conflict-free coloring with at most $5Delta(G)/2$ colors and conjectured that $Delta(G)+1$ colors suffice for every connected graph $G$ with $Delta(G)ge3$. Our first main result is that even for list-coloring, $leftlceil1.6550826Delta(G)+sqrtDelta(G)ightceil$ colors suffice for every graph $G$ with $Delta(G)ge10^9$; we also prove slightly weaker bounds for all graphs with $Delta(G)ge750$. These results follow from our more general framework on proper conflict-free list-coloring of a pair consisting of a graph $G$ and a ``conflict hypergraph $mathcalH$. As another corollary of our results in this general framework, every graph has a proper $(sqrt30+o(1))Delta(G{)}^{1.5}$-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'{a}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 $G$ has a fractional $(1+o(1))Delta(G)$-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.

This page was built for publication: Proper Conflict-free Coloring of Graphs with Large Maximum Degree

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6506972)