A quasi-polynomial chi-bound for P 6-free graphs
math.CO
Submitted: 2026-10-24
Updated: 2026-10-24
Comments: 16 pages
License: http://creativecommons.org/licenses/by/4.0/
The gist: In this paper we prove that every graph G with no induced six-vertex path satisfies χ(G) at most ω(G) c 2ω(G) for c=45/ 2(4/3)<109.
Abstract
In this paper we prove that every graph G with no induced six-vertex path satisfies χ(G) at most ω(G) c 2ω(G) for c=45/ 2(4/3)<109. The best previous bound was exponential in ω(G). Our result is the first quasi-polynomial bound for P 6-free graphs and generalizes the bound for P 5-free graphs by Scott, Seymour, and Spirkl [Polynomial bounds for chromatic number. IV. A near-polynomial bound for excluding the five-vertex path. Combinatorica, 43(5):845--852, 2023].
Related papers
- Three-ends Furstenberg estimates and approximate rectangles
- Multicolor Ramsey numbers of ordered matchings
- Exponential random graph models with soft clique constraints
- A Full-Sequence Quantitative Gap Between the Chromatic and Cochromatic Numbers of a Random Graph
- Ehrhart positivity for paving positroids
- Nonlinear lower-tail large deviations at criticality