Polynomial bounds for chromatic number. II. Excluding a star-forest

Author: 

Scott, A
Seymour, P
Spirkl, S

Last Updated: 

2021-08-22T21:13:58.073+01:00

abstract: 

The Gyarfas-Sumner conjecture says that for every forest $H$, there is a
function $f$ such that if $G$ is $H$-free then $\chi(G)\le f(\omega(G))$ (where
$\chi, \omega$ are the chromatic number and the clique number of $G$). Louis
Esperet conjectured that, whenever such a statement holds, $f$ can be chosen to
be a polynomial. The Gyarfas-Sumner conjecture is only known to be true for a
modest set of forests $H$, and Esperet's conjecture is known to be true for
almost no forests. For instance, it is not known when $H$ is a five-vertex
path. Here we prove Esperet's conjecture when each component of $H$ is a star.

Symplectic id: 

1189442

Download URL: 

Submitted to ORA: 

Not Submitted

Publication Type: 

Journal Article