Bounded chromatic number of graphs with small clique number and large minimum degree

Abstract

We prove that every triangle-free graph with minimum degree at least n/3 is $4$-colorable and thereby settle a problem of Brandt and Thomassé (2005) at the threshold n/3. The number four is best possible. For a positive integer-valued function f(n)=o(n), we relate the chromatic number of f(n)-vertex subgraphs of the Kneser graph $KG(n,f(n))$ to that of triangle-free graphs with minimum degree at least n/3−f(n). Consequently, for every 0<δ<1 and ε>0, and for all sufficiently large n, every n-vertex triangle-free graph with minimum degree at least n/3−n^1−δ has chromatic number at most 10³⁹¹+1+⌈(1+ε)(1−δ)/δ⌉. We also show that every sufficiently large n-vertex maximal triangle-free graph with minimum degree at least n/3−f(n) and chromatic number at least 10³⁹¹ contains a bipartite subgraph with parts of orders n/3−O(f(n)) and 2n/3−O(f(n)); the remaining induced subgraph admits a homomorphism to KG(n/3−O(f(n)),O(f(n))). Finally, we connect maximal K_r-free graphs with minimum degree at least (2r−5)/(2r−3)n−f(n) to K_r−1-free graphs and extend these results to K_r-free graphs. Our proofs employ the recent strong Brandt--Thomassé theorem of Łuczak, Polcyn, and Reiher.

Local Clique Covers and Chromatic Number
Akbar Davoodi
arXiv7 Sep 2026PreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
Polynomial minimum degree stability for $3$-chromatic graphs
Yisai Xue
arXiv2 Sep 2026PreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
On the k-Distance Chromatic Number of Unicyclic Graphs
Rosário Fernandes, Rúben Palma
Discrete Mathematics Letters25 Oct 2026Peer-reviewedCC BYFull textGeneral mathematicsDOAJ
Minimal Cayley graphs with large chromatic number
James Davies, Meike Hatzel, Liana Yepremyan
arXiv13 Oct 2026PreprintarXiv licenceFull textAlgebra & number theory Combinatorics & discrete mathematicsarXiv
Geometric triangle-free graphs of large chromatic number
István Tomon
arXiv6 Oct 2026PreprintCC BY 4.0Full textCombinatorics & discrete mathematics Geometry & topologyarXiv

Cite

BibTeX RIS

BibTeX

@misc{li2026bounded,
  title = {{Bounded chromatic number of graphs with small clique number and large minimum degree}},
  author = {Jiaao Li and Xinyuan Li},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2609.24097},
  eprint = {2609.24097},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.24097},
  note = {CC BY-NC-ND 4.0},
}

RIS

TY  - UNPB
TI  - Bounded chromatic number of graphs with small clique number and large minimum degree
AU  - Jiaao Li
AU  - Xinyuan Li
PY  - 2026
DA  - 2026/09/21
PB  - arXiv
DO  - 10.48550/arxiv.2609.24097
UR  - https://arxiv.org/abs/2609.24097
AB  - We prove that every triangle-free graph with minimum degree at least n/3 is $4$-colorable and thereby settle a problem of Brandt and Thomassé (2005) at the threshold n/3. The number four is best possible. For a positive integer-valued function f(n)=o(n), we relate the chromatic number of f(n)-vertex subgraphs of the Kneser graph $KG(n,f(n))$ to that of triangle-free graphs with minimum degree at least n/3−f(n). Consequently, for every 0<δ<1 and ε>0, and for all sufficiently large n, every n-vertex triangle-free graph with minimum degree at least n/3−n^1−δ has chromatic number at most 10^391+1+⌈(1+ε)(1−δ)/δ⌉. We also show that every sufficiently large n-vertex maximal triangle-free graph with minimum degree at least n/3−f(n) and chromatic number at least 10^391 contains a bipartite subgraph with parts of orders n/3−O(f(n)) and 2n/3−O(f(n)); the remaining induced subgraph admits a homomorphism to KG(n/3−O(f(n)),O(f(n))). Finally, we connect maximal K_r-free graphs with minimum degree at least (2r−5)/(2r−3)n−f(n) to K_r−1-free graphs and extend these results to K_r-free graphs. Our proofs employ the recent strong Brandt--Thomassé theorem of Łuczak, Polcyn, and Reiher.
ER  -

Abstract

Related

Cite