Publication details
Conflict-Free Coloring Planar Graphs with 4 Colors
| Authors | |
|---|---|
| Year of publication | 2026 |
| Type | Paper in proceedings |
| Conference | 34th Annual European Symposium on Algorithms (ESA 2026) |
| MU Faculty or unit | |
| Citation | |
| Doi | https://doi.org/10.4230/LIPIcs.ESA.2026.33 |
| Keywords | conflict-free coloring; planar graph; matching; Gallai-Edmonds decomposition |
| Description | 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. |
| Related projects: |