3-Colouring Graphs Excluding a Fixed Minor

Vida Dujmović, Hussein Houdrouge, Pat Morin

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…