{"id":"arxiv/2609.27152","url":"https://arxiv.org/abs/2609.27152","tags":["math.CO"],"score":0,"title":"Sparse Approximate Chromatic Profiles of Triangle-Free Graphs","domain":"math.CO","source":"arxiv","authors":["Guorong Gao","Jialin He"],"reviews":0,"subject":"math.CO","summary":"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,…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-09-22","reactions":{}}