Conflict-Free Coloring Planar Graphs with 4 Colors

D 2026

Conflict-Free Coloring Planar Graphs with 4 Colors

HLINĚNÝ, Petr a Lukáš MÁLIK

Základní údaje

Originální název

Conflict-Free Coloring Planar Graphs with 4 Colors

Autoři

HLINĚNÝ, Petr a Lukáš MÁLIK

Vydání

LIPIcs, Volume 388. Dagstuhl, Německo, 34th Annual European Symposium on Algorithms (ESA 2026), od s. "33:1"-"33:20", 20 s. 2026

Nakladatel

Schloss Dagstuhl – Leibniz-Zentrum für Informatik

Další údaje

Jazyk

angličtina

Typ výsledku

Stať ve sborníku

Obor

10201 Computer sciences, information science, bioinformatics

Stát vydavatele

Německo

Utajení

není předmětem státního či obchodního tajemství

Forma vydání

elektronická verze "online"

Označené pro přenos do RIV

Ano

Organizační jednotka

Fakulta informatiky

ISBN

978-3-95977-445-1

DOI

https://doi.org/10.4230/LIPIcs.ESA.2026.33

Klíčová slova anglicky

conflict-free coloring; planar graph; matching; Gallai-Edmonds decomposition

Příznaky

Mezinárodní význam, Recenzováno

Změněno: 1. 9. 2026 08:55, prof. RNDr. Petr Hliněný, Ph.D.

Anotace

V originále

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.

Návaznosti

GA26-21334S, projekt VaV

Název: New and traditional structural graph measures for logic and algorithms

Investor: Grantová agentura ČR, New and traditional structural graph measures for logic and algorithms

Citovat

HLINĚNÝ, Petr a Lukáš MÁLIK. Conflict-Free Coloring Planar Graphs with 4 Colors. Online. In 34th Annual European Symposium on Algorithms (ESA 2026). LIPIcs, Volume 388. Dagstuhl, Německo: Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2026, s. "33:1"-"33:20", 20 s. ISBN 978-3-95977-445-1. Dostupné z: https://doi.org/10.4230/LIPIcs.ESA.2026.33.

@inproceedings{2586820,
   author = {Hliněný, Petr and Málik, Lukáš},
   address = {Dagstuhl, Německo},
   booktitle = {34th Annual European Symposium on Algorithms (ESA 2026)},
   doi = {https://doi.org/10.4230/LIPIcs.ESA.2026.33},
   edition = {LIPIcs, Volume 388},
   keywords = {conflict-free coloring; planar graph; matching; Gallai-Edmonds decomposition},
   howpublished = {elektronická verze "online"},
   language = {eng},
   location = {Dagstuhl, Německo},
   isbn = {978-3-95977-445-1},
   pages = {"33:1"-"33:20"},
   publisher = {Schloss Dagstuhl – Leibniz-Zentrum für Informatik},
   title = {Conflict-Free Coloring Planar Graphs with 4 Colors},
   year = {2026}
}

TY  - CONF
ID  - 2586820
AU  - Hliněný, Petr - Málik, Lukáš
PY  - 2026
TI  - Conflict-Free Coloring Planar Graphs with 4 Colors
PB  - Schloss Dagstuhl – Leibniz-Zentrum für Informatik
CY  - Dagstuhl, Německo
SN  - 9783959774451
KW  - conflict-free coloring
KW  - planar graph
KW  - matching
KW  - Gallai-Edmonds decomposition
N2  - 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.
ER  -

HLINĚNÝ, Petr a Lukáš MÁLIK. Conflict-Free Coloring Planar Graphs with 4 Colors. Online. In \textit{34th Annual European Symposium on Algorithms (ESA 2026)}. LIPIcs, Volume 388. Dagstuhl, Německo: Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2026, s.~''33:1''-''33:20'', 20 s. ISBN~978-3-95977-445-1. Dostupné z: https://doi.org/10.4230/LIPIcs.ESA.2026.33.

Přehled o publikaci