3-Colouring Planar Graphs

2025/07/03 by Vida Dujmović, Pat Morin, Dujmović, Vida +5 · 1 citation
Computer Science · #Advanced Graph Theory Research #Graph Labeling and Dimension Problems

paper · pdf · doi:10.48550/arxiv.2507.03163

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].

Cited by

• Optimal tree-decompositions with bags of bounded pathwidth

Related

• Coloring outerplanar graphs and planar 3-trees with small monochromatic components
• Three coloring via triangle counting
• Multiple 3-Coloring, an Approach to 4-Coloring of Planar Graphs
• On the Three Colorability of Planar Graphs
• DP-3-colorability of planar graphs without cycles of length 4, 7 or 9