Sparse Approximate Chromatic Profiles of Triangle-Free Graphs

We prove a sparse version of the four-colour theorem of Brandt and Thomass\'{e}, answering a question of Allen, B\"ottcher, Kohayakawa and Roberts. For every fixed $0<\gamma \le 1/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/3+\gamma )pn$ can be made four-partite by deleting at most $\min \{C_{\gamma }n/p,(1/8+\gamma )p{n}^2\}$ edges. In fact, deleting at most $C_{\gamma }n/p$ edges yields a graph that admits a homomorphism to an Andr\'{a}sfai or Vega graph with certificate complexity at most $1/(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/p)$ edge deletions: $2/5$ for $q=2$, $10/29$ for $q=3$, and $1/3$ for every fixed $q\ge 4$. For every fixed $q\ge 2$ 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))p{n}^2$ edge deletions to become $q$-partite, showing that the coefficient $1/(2q)$ cannot be improved even under this stronger degree condition.