Polynomial Bounds for Chromatic Number. IV: A Near-polynomial Bound for Excluding the Five-vertex Path
Abstract
A graph G is H -free if it has no induced subgraph isomorphic to H. We prove that
a P5-free graph with clique number ω ≥ 3 has chromatic number at most ωlog2(ω).
The best previous result was an exponential upper bound (5/27)3ω, due to Esperet,
Lemoine, Maffray, and Morel. A polynomial bound would imply that the celebrated
Erd˝os-Hajnal conjecture holds for P5, which is the smallest open case. Thus, there is
great interest in whether there is a polynomial bound for P5-free graphs, and our result
is an attempt to approach that.
Collections
Cite this version of the work
Alex Scott, Paul Seymour, Sophie Spirkl
(2023).
Polynomial Bounds for Chromatic Number. IV: A Near-polynomial Bound for Excluding the Five-vertex Path. UWSpace.
http://hdl.handle.net/10012/20133
Other formats
The following license files are associated with this item: