Sparse Approximate Chromatic Profiles of Triangle-Free Graphs

Abstract

We prove a sparse version of the four-colour theorem of Brandt and Thomassé, answering a question of Allen, Böttcher, Kohayakawa and Roberts. For every fixed 0<γ≤1/10 and every p=p(n)∈(0,1], asymptotically almost surely every spanning triangle-free H⊆ G(n,p) with δ(H)≥(1/3+γ)pn can be made four-partite by deleting at most min{C_γn/p,(1/8+γ)pn²} edges. In fact, deleting at most C_γn/p edges yields a graph that admits a homomorphism to an Andrásfai or Vega graph with certificate complexity at most 1/(3γ). Together with matching lower bounds from random blow-ups, this structural result determines, uniformly in p, the minimum-degree thresholds for q-partiteness with O(n/p) edge deletions: 2/5 for q=2, 10/29 for q=3, and 1/3 for every fixed q≥4. For every fixed q≥2 and log n/n≪ p≪ n^−1/2, asymptotically almost surely G(n,p) contains a spanning triangle-free subgraph with minimum degree $(1-o(1))pn$ that requires (1/(2q)+o(1))pn² edge deletions to become q-partite, showing that the coefficient 1/(2q) cannot be improved even under this stronger degree condition.

Sparse chromatic graphs and the complete-graph triangle bound
Shuyan Chen
arXiv1 Sep 2026PreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
Geometric triangle-free graphs of large chromatic number
István Tomon
arXiv6 Oct 2026PreprintCC BY 4.0Full textCombinatorics & discrete mathematics Geometry & topologyarXiv
Bounds for the Vertex Chromatic Number of Connected Triangle-Free Graphs
Saieed Akbari, Arash Beikmohammadi
arXiv7 Sep 2026PreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv
The lower tail of triangle counts in sparse random graphs
Dong Huang, Shuangping Li
arXiv23 Oct 2026PreprintarXiv licenceFull textCombinatorics & discrete mathematics ProbabilityarXiv
On the k-Distance Chromatic Number of Unicyclic Graphs
Rosário Fernandes, Rúben Palma
Discrete Mathematics Letters25 Oct 2026Peer-reviewedCC BYFull textGeneral mathematicsDOAJ

Cite

BibTeX RIS

BibTeX

@misc{gao2026sparse,
  title = {{Sparse Approximate Chromatic Profiles of Triangle-Free Graphs}},
  author = {Guorong Gao and Jialin He},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2609.27152},
  eprint = {2609.27152},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.27152},
  note = {CC BY 4.0},
}

RIS

TY  - UNPB
TI  - Sparse Approximate Chromatic Profiles of Triangle-Free Graphs
AU  - Guorong Gao
AU  - Jialin He
PY  - 2026
DA  - 2026/09/22
PB  - arXiv
DO  - 10.48550/arxiv.2609.27152
UR  - https://arxiv.org/abs/2609.27152
AB  - We prove a sparse version of the four-colour theorem of Brandt and Thomassé, answering a question of Allen, Böttcher, Kohayakawa and Roberts. For every fixed 0<γ≤1/10 and every p=p(n)∈(0,1], asymptotically almost surely every spanning triangle-free H⊆ G(n,p) with δ(H)≥(1/3+γ)pn can be made four-partite by deleting at most min{C_γn/p,(1/8+γ)pn^2} edges. In fact, deleting at most C_γn/p edges yields a graph that admits a homomorphism to an Andrásfai or Vega graph with certificate complexity at most 1/(3γ). Together with matching lower bounds from random blow-ups, this structural result determines, uniformly in p, the minimum-degree thresholds for q-partiteness with O(n/p) edge deletions: 2/5 for q=2, 10/29 for q=3, and 1/3 for every fixed q≥4. For every fixed q≥2 and log n/n≪ p≪ n^−1/2, asymptotically almost surely G(n,p) contains a spanning triangle-free subgraph with minimum degree $(1-o(1))pn$ that requires (1/(2q)+o(1))pn^2 edge deletions to become q-partite, showing that the coefficient 1/(2q) cannot be improved even under this stronger degree condition.
ER  -

Abstract

Related

Cite