Skip to content
DraconiticResearch
Search Sources API
203,234 studies31 sourcesUpdated 43 min ago
PreprintarXiv licencearXiv

Polylogarithmic bound for the Gyárfás-Sumner conjecture

  • Martin Bierbaumer
  • Matija Bucić
Open at sourcePDFDOICite

Abstract

The classical Gyárfás-Sumner conjecture asserts that for any fixed forest F, any graph G not containing F as an induced subgraph, with bounded clique number ω(G), has bounded chromatic number χ(G). Recently, Nguyen, Scott, and Seymour proved that every such graph has chromatic number at most |G|o(1). We improve this bound to a polylogarithmic one (log |G|)O(1).

Related

  1. A polylogarithmic bound for list replicability
    Ari Blondal, Hamed Hatami, Pooya Hatami +2
    arXivPreprintCC BY-NC-SA 4.0Full textCombinatorics & discrete mathematicsStatisticsarXiv
  2. An Improvement to the Upper Bound for Marton's Covering Conjecture
    Zhao Song, Song Yue
    arXivPreprintCC BY-NC-SA 4.0Full textCombinatorics & discrete mathematicsarXiv
  3. An Improved Bound for Smith's Longest Cycles Conjecture via a Forbidden Subdivision
    Douglas M. Chen
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv
  4. Odd-ordered Cayley graphs satisfy Erdős--Gyárfás
    Michael C. Burkhart
    arXivPreprintarXiv licenceFull textAlgebra & number theoryCombinatorics & discrete mathematicsarXiv
  5. A near-linear upper bound for Burr's conjecture
    Liangdong Fan, Junying Lu, Yaojun Chen
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv

Cite

BibTeXRIS
BibTeX
@misc{bierbaumer2026polylogarithmic,
  title = {{Polylogarithmic bound for the Gyárfás-Sumner conjecture}},
  author = {Martin Bierbaumer and Matija Bucić},
  howpublished = {arXiv},
  year = {2026},
  month = nov,
  doi = {10.48550/arxiv.2611.06699},
  eprint = {2611.06699},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.06699},
}
RIS
TY  - UNPB
TI  - Polylogarithmic bound for the Gyárfás-Sumner conjecture
AU  - Martin Bierbaumer
AU  - Matija Bucić
PY  - 2026
DA  - 2026/11/04
PB  - arXiv
DO  - 10.48550/arxiv.2611.06699
UR  - https://arxiv.org/abs/2611.06699
AB  - The classical Gyárfás-Sumner conjecture asserts that for any fixed forest F, any graph G not containing F as an induced subgraph, with bounded clique number ω(G), has bounded chromatic number χ(G). Recently, Nguyen, Scott, and Seymour proved that every such graph has chromatic number at most |G|^o(1). We improve this bound to a polylogarithmic one (log |G|)^O(1).
ER  -