Publications

Home Activities Publications

Abstract: A proper conflict-free c-coloring of a graph is a proper c-coloring such that each nonisolated 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 5coloring. Caro, Petru & scaron;evski, and & Scaron;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 is an element of {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 mad(G) <= (4c)/(c+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) < (12)/(5) 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. (c) 2024 Elsevier B.V. All rights are reserved, including those for text and data mining, AI training, and similar technologies.

List