{
  "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<γ\\le1/10$ and every $p=p(n)\\in(0,1]$, asymptotically almost surely every spanning triangle-free $H\\subseteq G(n,p)$ with $δ(H)\\ge(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\\ge4$. For every fixed $q\\ge2$ and $\\log n/n\\ll p\\ll 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.",
  "abstract_shown": true,
  "affiliations": [],
  "article_type": null,
  "arxiv": "2609.27152",
  "author_total": 2,
  "authors": [
    {
      "name": "Guorong Gao"
    },
    {
      "name": "Jialin He"
    }
  ],
  "bibtex": "https://research.draconitic.com/paper/fce92909dt04g.bib",
  "cited_by": 0,
  "doi": "10.48550/arxiv.2609.27152",
  "fulltext_url": null,
  "id": "fce92909dt04g",
  "issns": [],
  "landing_url": "https://arxiv.org/abs/2609.27152",
  "language": null,
  "licence": "CC-BY-4.0",
  "licence_label": "CC BY 4.0",
  "licence_source": "article",
  "licence_url": "http://creativecommons.org/licenses/by/4.0/",
  "metadata_licence": "CC0-1.0",
  "native_subjects": [
    [
      "arxiv",
      "math.CO"
    ]
  ],
  "openalex": null,
  "pdf_url": "https://arxiv.org/pdf/2609.27152",
  "pmcid": null,
  "pmid": null,
  "published": "2026-09-22",
  "publisher": null,
  "ris": "https://research.draconitic.com/paper/fce92909dt04g.ris",
  "sources": [
    {
      "first_seen": "2026-10-30T12:24:00Z",
      "native_id": "2609.27152",
      "source": "arxiv",
      "url": "https://arxiv.org/abs/2609.27152"
    }
  ],
  "subjects": [
    {
      "field": "mathematics",
      "origin": "arxiv:math.CO",
      "subfield": "combinatorics"
    }
  ],
  "title": "Sparse Approximate Chromatic Profiles of Triangle-Free Graphs",
  "title_text": "Sparse Approximate Chromatic Profiles of Triangle-Free Graphs",
  "type": "preprint",
  "updated_at": "2026-10-30T12:24:00Z",
  "url": "https://research.draconitic.com/paper/fce92909dt04g",
  "venue": "arXiv",
  "versions": []
}