DROPS

Document

DOI: 10.4230/LIPIcs.ESA.2026.33

Conflict-Free Coloring Planar Graphs with 4 Colors

Authors: Petr Hliněný and Lukáš Málik

Published in: LIPIcs, Volume 388, 34th Annual European Symposium on Algorithms (ESA 2026)

Abstract

We efficiently conflict-free color every planar graph with 4 colors. An (open-neighborhood) conflict-free coloring assigns colors to vertices in a way that every vertex v has a neighbor w such that the color of w is distinct from the colors of the other neighbors of v (i.e., the color of w is unique in the open neighborhood of v). A previous best upper bound on the conflict-free chromatic number of planar graphs was 5, and it is known that 4 colors are sometimes necessary. Deciding whether, e.g., a planar graph admits a conflict-free coloring with 3 colors is NP-complete. Our approach uses a refined variant of the classical Gallai-Edmonds decomposition and the Four Color Theorem. In fact, our result is equivalent to the Four Color Theorem.

Cite as

Petr Hliněný and Lukáš Málik. Conflict-Free Coloring Planar Graphs with 4 Colors. In 34th Annual European Symposium on Algorithms (ESA 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 388, pp. 33:1-33:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{hlineny_et_al:LIPIcs.ESA.2026.33,
  author =	{Hlin\v{e}n\'{y}, Petr and M\'{a}lik, Luk\'{a}\v{s}},
  title =	{{Conflict-Free Coloring Planar Graphs with 4 Colors}},
  booktitle =	{34th Annual European Symposium on Algorithms (ESA 2026)},
  pages =	{33:1--33:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-445-1},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{388},
  editor =	{Bille, Philip and Pettie, Seth and Storandt, Sabine},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2026.33},
  URN =		{urn:nbn:de:0030-drops-271696},
  doi =		{10.4230/LIPIcs.ESA.2026.33},
  annote =	{Keywords: conflict-free coloring, planar graph, matching, Gallai-Edmonds decomposition}
}

Search Results

Documents authored by Málik, Lukáš

Conflict-Free Coloring Planar Graphs with 4 Colors

Abstract

Cite as

Thanks for your feedback!

Could not send message