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

@misc{sedlar2026four,
  title = {{Four colours are needed for closed-neighbourhood conflict-free colouring of all planar graphs}},
  author = {Jelena Sedlar and Riste Škrekovsk},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.22559},
  eprint = {2610.22559},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.22559},
}

TY  - UNPB
TI  - Four colours are needed for closed-neighbourhood conflict-free colouring of all planar graphs
AU  - Jelena Sedlar
AU  - Riste Škrekovsk
PY  - 2026
DA  - 2026/10/15
PB  - arXiv
DO  - 10.48550/arxiv.2610.22559
UR  - https://arxiv.org/abs/2610.22559
AB  - 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 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 such 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 planar graph on $25$ vertices that needs four colours. Further, we give critical planar graphs on $25$ vertices with $52$ and with $51$ edges, an infinite family of plane triangulations that need four colours, and an infinite family of critical examples.
ER  -