3-Colouring Planar Graphs

Key Points

Every n-vertex planar graph is shown to be 3-colourable with monochromatic components of size O(n^{4/9}).
This shows a significant improvement over the previous bound of O(n^{1/2}), indicating stronger colourability.
The analysis processes n vertices systematically, leveraging properties unique to planar graphs.
These results could lead to new applications in graph theory and algorithm design in combinatorics.

Abstract

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.

Read Full Paperexternally

Bookmark

View Full Paper

Cite This Study

Dujmović et al. (Thu,) studied this question.

synapsesocial.com/papers/68f5fcdc8d54a28a75cf2452 https://doi.org/https://doi.org/10.48550/arxiv.2507.03163

Also Consider

Synapse has enriched 5 closely related papers on similar clinical questions. Consider them for comparative context:

Bookmark

View Full Paper