{"id":"arxiv/2606.25988","url":"https://arxiv.org/abs/2606.25988","tags":["math.CO","cs.DM"],"score":0,"title":"Conflict-Free Coloring Planar Graphs with 4 Colors","domain":"math.CO","source":"arxiv","authors":["Petr Hliněný","Lukáš Málik"],"reviews":0,"subject":"math.CO","summary":"We efficiently conflict-free color every planar graph with 4 colors. An (open-neighborhood) conflict-free coloring assigns colors to vertices in a way that every vertex v has a neighbor w such that the color of w is distinct from the colors of the other neighbors of v (i.e., the color of w is unique in the open neighborhood of v). A previous best upper bound on the conflict-free chromatic number of planar graphs was 5, and it is known that 4 colors are sometimes necessary. Deciding whether, e.g., a planar graph admits a conflict-free coloring with 3 colors is NP-complete. Our approach uses a…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-06-24","reactions":{}}