Back to Search
Start Over
Polynomial bounds for chromatic number VI. Adding a four-vertex path
- Source :
- European Journal of Combinatorics, Volume 110, May 2023, 103710
- Publication Year :
- 2022
-
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\'arf\'as-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.<br />Comment: Accepted manuscript; see DOI for journal version
- Subjects :
- Mathematics - Combinatorics
Subjects
Details
- Database :
- arXiv
- Journal :
- European Journal of Combinatorics, Volume 110, May 2023, 103710
- Publication Type :
- Report
- Accession number :
- edsarx.2202.10412
- Document Type :
- Working Paper
- Full Text :
- https://doi.org/10.1016/j.ejc.2023.103710