Sparse Approximate Chromatic Profiles of Triangle-Free Graphs

Source 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.