{"id":"arxiv/2607.02159","url":"https://arxiv.org/abs/2607.02159","tags":["math.CO","cs.DM"],"score":0,"title":"3-Colouring Graphs Excluding a Fixed Minor","domain":"math.CO","source":"arxiv","authors":["Vida Dujmović","Hussein Houdrouge","Pat Morin"],"reviews":0,"subject":"math.CO","summary":"We show that, for every fixed graph $H$, every $n$-vertex graph $G$ that excludes $H$ as a minor is $3$-colourable with clustering $O_H(n^{4/9})$. That is, there exists a function $f$ such that for every graph $H$, every $n\\ge 1$, every $n$-vertex graph $G$ that excludes $H$ as a minor has a vertex colouring with $3$ colours in which each monochromatic component has size at most $f(H)\\cdot n^{4/9}$. This generalizes a recent result of Dujmović, Morin, Norin, and Wood (\\textit{arXiv}:2507.03163) from planar graphs to all proper minor-closed graph classes and is the first improvement on…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-07-02","reactions":{}}