Paperlane

no. 16 · Tuesday 17 November 2026

Four colours are needed for closed-neighbourhood conflict-free colouring of planar graphs

Jelena Sedlar and Riste Škrekovski

math.CO · v2 · 16 pp

Abstract

A colouring of the vertices of a graph is conflict-free with respect to closed neighbourhoods if every closed neighbourhood contains a colour that appears on exactly one of its vertices. The colouring need not be proper. Every planar graph has such a colouring with four colours. Fabrici, Lužar, Rindošová and Soták [Proper conflict-free and unique-maximum colorings of planar graphs with respect to neighborhoods, \emph{Discrete Appl.\ Math.}\ \textbf{324} (2023) 80–92] conjectured that three colours always suffice. We disprove this conjecture. We give a simple gadget construction that turns every planar graph of chromatic number four into a planar graph with no conflict-free colouring with three colours. This also shows that it is NP-complete to decide whether three colours suffice for a planar graph. We also give a critical planar graph on $25$ vertices and $51$ edges that needs four colours, with a proof that can be checked by hand. Finally, we give an infinite family of plane triangulations that need four colours, and an infinite family of critical examples.

comments
16 pages
fields
Combinatorics
pdf ↗ page arXiv:2610.22559 ↗