A conflict-free coloring assigns colors to the members of a set so that each specified range contains a color used exactly once. For closed-neighborhood conflict-free coloring of a graph, the ranges are the closed neighborhoods of its vertices. Thus every graph vertex, together with its neighbors, must contain a uniquely occurring color. The coloring need not be a proper coloring (Sedlar and Škrekovski 2026).
Every proper coloring is closed-neighborhood conflict-free, so the four-color theorem gives an upper bound of four colors for planar graphs. Sedlar and Škrekovski (2026) disproved the conjecture that three always suffice by constructing a planar graph on 25 vertices requiring four colors. They also proved that deciding whether three colors suffice is NP-complete even for planar graphs of maximum vertex degree at most 24. Sedlar and Škrekovski (2026) acknowledge Claude assistance with arguments and checking, and state that they verified the mathematics.
