= Semi-random palette refinement for triangle-free colouring
Maintain lists of available colours, tentatively colour small random portions, erase conflicts and prune colours used by neighbours. In a <triangle-free graph>, a vertex's neighbours form an <independent set>, which enables local estimates. Track list size and average remaining neighbour congestion per colour; prune unusually congested colours before the next round. Concentration and the <Lovász local lemma> preserve these invariants until lists have enough slack for completion. Tracking averages matters because triangle-free graphs can still contain many four-cycles and need not have uniform per-colour congestion.
Back to article page
