Sparse chromatic graphs and the complete-graph triangle bound
Abstract
We prove that there is an absolute constant c>0 such that every graph of chromatic number at least r and at most cr3log2 r edges contains at least binom r3 triangles. The proof has three ingredients. First, a sparse-core argument based on a triangle-sensitive coloring estimate of Harris extracts, from any counterexample, an induced subgraph of order O(r) and chromatic number at least (1−η)r. Second, we prove an order-uniform stability theorem: for every β>0 there is γ>0, independent of the constant in the linear order bound, such that every sufficiently large s-critical graph J of order O(s) with ω(J)≤ (1−β)s has at least binom s3+γs3 triangles. The proof combines the excess method and the modified-independent-set argument of Fox, Tidor, and Zhang. Third, we prove the exact bound when the graph contains a clique of order at least (1−δ)r. This uses a new dense common-palette list analogue of Harris's edge--triangle estimate: if every list occupies a fixed positive proportion of a common palette, then the edge-triangle coloring bound survives up to a constant factor.
Related
- Sparse Approximate Chromatic Profiles of Triangle-Free Graphs
- Geometric triangle-free graphs of large chromatic number
- Bounds for the Vertex Chromatic Number of Connected Triangle-Free Graphs
- The Game Chromatic Number of Complete Multipartite Graphs with Singletons and Large Parts
- The 3-Color 2-Chromatic Gallai-Ramsey Number for Complete Graphs
BibTeX
@misc{chen2026sparse,
title = {{Sparse chromatic graphs and the complete-graph triangle bound}},
author = {Shuyan Chen},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.26247},
eprint = {2609.26247},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.26247},
}
RIS
TY - UNPB
TI - Sparse chromatic graphs and the complete-graph triangle bound
AU - Shuyan Chen
PY - 2026
DA - 2026/09/01
PB - arXiv
DO - 10.48550/arxiv.2609.26247
UR - https://arxiv.org/abs/2609.26247
AB - We prove that there is an absolute constant c>0 such that every graph of chromatic number at least r and at most cr^3log^2 r edges contains at least binom r3 triangles. The proof has three ingredients. First, a sparse-core argument based on a triangle-sensitive coloring estimate of Harris extracts, from any counterexample, an induced subgraph of order O(r) and chromatic number at least (1−η)r. Second, we prove an order-uniform stability theorem: for every β>0 there is γ>0, independent of the constant in the linear order bound, such that every sufficiently large s-critical graph J of order O(s) with ω(J)≤ (1−β)s has at least binom s3+γs^3 triangles. The proof combines the excess method and the modified-independent-set argument of Fox, Tidor, and Zhang. Third, we prove the exact bound when the graph contains a clique of order at least (1−δ)r. This uses a new dense common-palette list analogue of Harris's edge--triangle estimate: if every list occupies a fixed positive proportion of a common palette, then the edge-triangle coloring bound survives up to a constant factor.
ER -