Sparse Approximate Chromatic Profiles of Triangle-Free Graphs

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<\gamma \le 1\mathrm{/}10$ and every $p=p(n)\in (0,1]$, asymptotically almost surely every spanning triangle-free $H\subseteq G(n,p)$ with $\delta (H)\ge (1\mathrm{/}3+\gamma )pn$ can be made four-partite by deleting at most $\min \{C_{\gamma }n\mathrm{/}p,(1\mathrm{/}8+\gamma )p{n}^2\}$ edges. In fact, deleting at most $C_{\gamma }n\mathrm{/}p$ edges yields a graph that admits a homomorphism to an Andrásfai or Vega graph with certificate complexity at most $1\mathrm{/}(3\gamma )$. 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\mathrm{/}p)$ edge deletions: $2\mathrm{/}5$ for $q=2$, $10\mathrm{/}29$ for $q=3$, and $1\mathrm{/}3$ for every fixed $q\ge 4$. For every fixed $q\ge 2$ and $\log n\mathrm{/}n\ll p\ll n^{-1\mathrm{/}2}$, asymptotically almost surely $G(n,p)$ contains a spanning triangle-free subgraph with minimum degree $(1-o(1))pn$ that requires $(1\mathrm{/}(2q)+o(1))p{n}^2$ edge deletions to become $q$-partite, showing that the coefficient $1\mathrm{/}(2q)$ cannot be improved even under this stronger degree condition.