Polynomial bounds for chromatic number. III. Excluding a double star
Alex Scott, Paul D. Seymour, Sophie Spirkl · Journal of Graph Theory · 2022
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 , there is a function such that if does not contain as an induced subgraph then (where are the chromatic number and the clique number of ). Here we prove that can be chosen to be a polynomial.