Informace o publikaci
Conflict-Free Coloring Planar Graphs with 4 Colors
| Autoři | |
|---|---|
| Rok publikování | 2026 |
| Druh | Stať ve sborníku |
| Konference | 34th Annual European Symposium on Algorithms (ESA 2026) |
| Fakulta / Pracoviště MU | |
| Citace | |
| Doi | https://doi.org/10.4230/LIPIcs.ESA.2026.33 |
| Klíčová slova | conflict-free coloring; planar graph; matching; Gallai-Edmonds decomposition |
| Popis | 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. |
| Související projekty: |