A quasi-polynomial $χ$-bound for $P_6$-free graphs
In this paper we prove that every graph $G$ with no induced six-vertex path satisfies $χ(G)\le ω(G)^{c\log_2ω(G)}$ for $c=45/\log_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. {\em Combinatorica}, 43(5):845--852, 2023].
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2610.33407
curl -X POST /api/v1/records/arxiv/2610.33407/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2610.33407/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'