Proper conflict-free coloring of sparse graphs

MaRDI QIDQ6395168zbMATH OpenFDO

Authors Eun-Kyung Cho, Ilkyoo Choi, Hyemin Kwon, Boram Park

Publication date 30 March 2022

Abstract: A {it proper conflict-free $c$-coloring} of a graph is a proper $c$-coloring such that each non-isolated vertex has a color appearing exactly once on its neighborhood. This notion was formally introduced by Fabrici et al., who proved that planar graphs have a proper conflict-free 8-coloring and constructed a planar graph with no proper conflict-free 5-coloring. Caro, Petruv{s}evski, and v{S}krekovski investigated this coloring concept further, and in particular studied upper bounds on the maximum average degree that guarantees a proper conflict-free $c$-coloring for $cin4,5,6$. Along these lines, we completely determine the threshold on the maximum average degree of a graph $G$, denoted $mad(G)$, that guarantees a proper conflict-free $c$-coloring for all $c$ and also provide tightness examples. Namely, for $cgeq5$ we prove that a graph $G$ with $mad(G)leqfrac4cc+2$ has a proper conflict-free $c$-coloring, unless $G$ contains a $1$-subdivision of the complete graph on $c+1$ vertices. When $c=4$, we show that a graph $G$ with $mad(G)<frac125$ has a proper conflict-free $4$-coloring, unless $G$ contains an induced $5$-cycle. In addition, we show that a planar graph with girth at least 5 has a proper conflict-free $7$-coloring.

This page was built for publication: Proper conflict-free coloring of sparse graphs

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