Metraipolis › archive › dc_4d38e91daab7
Bounded chromatic number of graphs with small clique number and large minimum degree — arXiv:2609.24097
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2609.24097
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-09T21:45:05.943Z
- SHA-256 of the archived text
ed3787271b2842f47e5bda3c69d8b58dddcdfda4558639f90f4e4423db6970b4- Stable URL of this page
https://metraipolis.com/documento/dc_4d38e91daab7
How to cite
Bounded chromatic number of graphs with small clique number and large minimum degree — arXiv:2609.24097 — arXiv (en), https://arxiv.org/abs/2609.24097 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_4d38e91daab7 (Metraipolis archive dc_4d38e91daab7, sha256 ed3787271b2842f47e5bda3c69d8b58dddcdfda4558639f90f4e4423db6970b4)
BibTeX
@misc{dc4d38e91daab7,
title = {Bounded chromatic number of graphs with small clique number and large minimum degree — arXiv:2609.24097},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2609.24097},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_4d38e91daab7; sha256 ed3787271b2842f47e5bda3c69d8b58dddcdfda4558639f90f4e4423db6970b4},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.24097. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
We prove that every triangle-free graph with minimum degree at least $\frac{n}{3}$ is $4$-colorable and thereby settle a problem of Brandt and Thomassé (2005) at the threshold $\frac{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 $\frac{n}{3}-f(n)$. Consequently, for every $0<\delta<1$ and $\varepsilon>0$, and for all sufficiently large $n$, every $n$-vertex triangle-free graph with minimum degree at least $\frac{n}{3}-n^{1-\delta}$ has chromatic number at most $10^{391}+1+\left\lceil{(1+\varepsilon)(1-\delta)}/{\delta}\right\rceil$. We also show that every sufficiently large $n$-vertex maximal triangle-free graph with minimum degree at least $\frac{n}{3}-f(n)$ and chromatic number at least $10^{391}$ contains a bipartite subgraph with parts of orders $\frac{n}{3}-O(f(n))$ and $\frac{2n}{3}-O(f(n))$; the remaining induced subgraph admits a homomorphism to $KG(\frac{n}{3}-O(f(n)),O(f(n)))$. Finally, we connect maximal $K_r$-free graphs with minimum degree at least $\frac{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.
Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-22 in math.CO).
Categorie arXiv: Combinatorics (math.CO).
Pagina del lavoro: https://arxiv.org/abs/2609.24097 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-09T21:26:41.149Z dalla pagina https://arxiv.org/catchup/math.CO/2026-09-22?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).