A quasi-polynomial chi-bound for P 6-free graphs

arXiv:2610.33407 · math.CO · Submitted 2026-10-24 · Read on arXiv

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