Polynomial bounds for chromatic number. III. Excluding a double star

Abstract

A double star is a tree with two internal vertices. It is known that the Gyárfás-Sumner conjecture holds for double stars, that is, for every double star $H$, there is a function $f$ such that if $G$ does not contain $H$ as an induced subgraph then $\chi (G)\le f(\omega (G))$ (where $\chi ,\omega$ are the chromatic number and the clique number of $G$). Here we prove that $f$ can be chosen to be a polynomial.