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

Source: arxiv.org/abs/2611.06699

Martin Bierbaumer, Matija Bucić

arXivarxiv/2611.06699Nov 4, 2026math.COscore 0

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)}$.

JSON

Comments and reviews

No comments yet.

API

curl /api/v1/records/arxiv/2611.06699
curl -X POST /api/v1/records/arxiv/2611.06699/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2611.06699/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'