Polynomial bounds for chromatic number VI. Adding a four-vertex path

Abstract

A class of graphs is $\chi$-bounded if there is a function $f$ such that every graph $G$ in the class has chromatic number at most $f(\omega (G))$, where $\omega (G)$ is the clique number of $G$; the class is polynomially $\chi$-bounded if $f$ can be taken to be a polynomial. The Gyárfás-Sumner conjecture asserts that, for every forest $H$, the class of $H$-free graphs (graphs with no induced copy of $H$) is $\chi$-bounded. Let us say a forest $H$ is good if it satisfies the stronger property that the class of $H$-free graphs is polynomially $\chi$-bounded. Very few forests are known to be good: for example, it is open for the five-vertex path. Indeed, it is not even known that if every component of a forest $H$ is good then $H$ is good, and in particular, it was not known that the disjoint union of two four-vertex paths is good. Here we show the latter, and more generally, that if $H$ is good then so is the disjoint union of $H$ and a four-vertex path. We also prove a more general result: if every component of $H_1$ is good, and $H_2$ is any path (or broom) then the class of graphs that are both $H_1$-free and $H_2$-free is polynomially $\chi$-bounded.

Accepted manuscript; see DOI for journal version

Cited by in corpus (1)

• Reuniting $\chi$-boundedness with polynomial $\chi$-boundedness