no. 16 · Tuesday 17 November 2026
Four colours are needed for closed-neighbourhood conflict-free colouring of planar graphs
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