pipette
ENEnglish

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

Jelena Sedlar, Riste \v{S}krekovsk

Preprint

En palabras de los autores

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\v{z}ar, Rindo\v{s}ov\'a and Sot\'ak 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 vertices that needs four colours. Further, we give critical planar graphs on vertices with and with edges, an infinite family of plane triangulations that need four colours, and an infinite family of critical examples.

Resultado principalEl resumen no menciona limitaciones.

Apareció: lunes, 19 de octubre. arXiv. Preprint, todavía sin revisión por pares.

Comentario de los autores: 14 pages