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

DOI10.1016/J.EJC.2023.103710arXiv2202.10412MaRDI QIDQ6391768

Sophie Spirkl, Alex Scott, Maria Chudnovsky, Paul Seymour

Publication date: 21 February 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.

Mathematics Subject Classification ID

Graph polynomials (05C31) Coloring of graphs and hypergraphs (05C15)

This page was built for publication: Polynomial bounds for chromatic number VI. Adding a four-vertex path

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6391768)