October 20, 2025Open Access

3-Colouring Planar Graphs

View Full Paper

Ask AI

Bookmark

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.

Implication

This study shows every n-vertex planar graph is 3-colourable, with component size bounds improving previous results.

Abstract

We show that every n-vertex planar graph is 3-colourable with monochromatic components of size O(n4/9). The best previous bound was O(n1/2) due to Linial, Matoušek, Sheffet and Tardos [Combin. Probab. Comput., 2008].

Discussion

No takes yet. Share an insight, caveat, or question.

Cite This Study

Dujmović et al. (2025) studied this question.

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

View Full Paper

Ask AI

Bookmark

Implication

This study shows every n-vertex planar graph is 3-colourable, with component size bounds improving previous results.

3-Colouring Planar Graphs

Key Points

Implication

Abstract

Discussion

Cite This Study

3-Colouring Planar Graphs

Key Points

Implication

Abstract

Discussion

Cite This Study

Keep reading

Keep reading