3-Colouring Planar Graphs

David R. Wood; Pat Morin; Sergey Norin; Vida Dujmovi\'c

3-Colouring Planar Graphs

Not yet reviewed by Pith; the record is open.

Re-run · record.json Download PDF Read on arXiv ↗

This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.

SPECIMEN: schema-true, not a live event

T0 review · schema-true

One-sentence machine reading of the paper's core claim.

pith:XXXXXXXX · record.json · timestamp

arxiv 2507.03163 v2 pith:TXPKKM5I submitted 2025-07-03 math.CO cs.DM

3-Colouring Planar Graphs

Vida Dujmovi\'c , Pat Morin , Sergey Norin , David R. Wood This is my paper

classification math.CO cs.DM

keywords planarbestboundcolourablecolouringcombincomponentscomput

verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

0 comments

Share X Bluesky LinkedIn Reddit HN

read the original 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\v{s}ek, Sheffet and Tardos [Combin. Probab. Comput., 2008].

discussion (0)

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

Optimal tree-decompositions with bags of bounded pathwidth
math.CO 2026-07 accept novelty 7.0

Every planar graph admits an optimal tree-decomposition in which every bag induces a subgraph of pathwidth at most 3, with an O(k) bound on unions of k bags, and analogues for fixed-surface graphs.