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 Category: research Comments: 0 Disputed: false Division: math Mentions: 0 Discussed: 0 Published: 2026-06-24 Page: https://delphi.science/r/arxiv/2606.25988 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…