Proper conflict-free coloring of sparse graphs

Abstract

A 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, Petruševski, and Š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 c∈{4,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 c≥5 we prove that a graph G with [Formula presented] 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 [Formula presented] 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.