3-Colouring Planar Graphs
arXiv:2507.0316311.31 citationsh-index: 18
Predicted impact top 10% in CO · last 90 daysOriginality Synthesis-oriented
AI Analysis
This is an incremental improvement for graph theorists working on coloring problems.
The authors improved the bound on the size of monochromatic components in 3-colorings of planar graphs from O(n^{1/2}) to O(n^{4/9}).
We show that every $n$-vertex planar graph is 3-colourable with monochromatic components of size $O(n^{4/9})$. The best previous bound was $O(n^{1/2})$ due to Linial, Matoušek, Sheffet and Tardos [Combin. Probab. Comput., 2008].