Back to Search Start Over

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

Authors :
Chudnovsky, Maria
Scott, Alex
Seymour, Paul
Spirkl, Sophie
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

Subjects :
Mathematics - Combinatorics

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