Skip to content
DraconiticResearch
Search Sources API
203,234 studies31 sourcesUpdated 39 min ago
PreprintCC BY 4.0arXiv

A quasi-polynomial χ-bound for P6-free graphs

  • Shenwei Huang
  • Yidong Zhou
  • Yuwen Zhou
Open at sourcePDFDOICite

Abstract

In this paper we prove that every graph G with no induced six-vertex path satisfies χ(G)≤ ω(G)clog2ω(G) for c=45/log2(4/3)<109. The best previous bound was exponential in ω(G). Our result is the first quasi-polynomial bound for P6-free graphs and generalizes the bound for P5-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].

Related

  1. An optimal χ-bound for {P7, diamond}-free graphs
    Kaiyang Lan, Hongyang Wang
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  2. A sharp bound on the binding number of Kk-free graphs and the Brandt conjecture
    Jifu Lin, Heng Yang
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  3. Polynomial pathwidth for graphs vertex-coverable by few shortest paths and algorithms for quasi-shortest path covers
    Li-Hsuan Chen, Florent Foucaud, Ling-Ju Hung +3
    HALPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsHALarXiv
  4. A sharp bound for the least signless Laplacian eigenvalue of triangle-free graphs
    Dongxiu Cai, Zhengbo Chen, Xiao-Dong Zhang
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  5. A Robust Bollobás-Nikiforov Bound for Graphs Close to Triangle-Free Graphs
    Yong Lu
    The Electronic Journal of CombinatoricsPeer-reviewedCC BY 4.0Full textCombinatorics & discrete mathematicsCrossref

Cite

BibTeXRIS
BibTeX
@misc{huang2026quasipolynomial,
  title = {{A quasi-polynomial $χ$-bound for $P_6$-free graphs}},
  author = {Shenwei Huang and Yidong Zhou and Yuwen Zhou},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.33407},
  eprint = {2610.33407},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.33407},
  note = {CC BY 4.0},
}
RIS
TY  - UNPB
TI  - A quasi-polynomial χ-bound for P_6-free graphs
AU  - Shenwei Huang
AU  - Yidong Zhou
AU  - Yuwen Zhou
PY  - 2026
DA  - 2026/10/24
PB  - arXiv
DO  - 10.48550/arxiv.2610.33407
UR  - https://arxiv.org/abs/2610.33407
AB  - In this paper we prove that every graph G with no induced six-vertex path satisfies χ(G)≤ ω(G)^clog_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].
ER  -