Strong Brandt‐Thomassé Theorems

ABSTRACT Solving a long standing conjecture of Erdős and Simonovits, Brandt and Thomassé proved that the chromatic number of each triangle‐free graph such that is at most four. In fact, they showed the much stronger result that every maximal triangle‐free graph satisfying this minimum degree condition is a blow‐up of either an Andrásfai or a Vega graph. Here we establish the same structural conclusion on under the weaker assumption that for every sequence of vertices has a subsequence of length with a common neighbour. In forthcoming work this will be used to solve an old problem of Andrásfai in Ramsey‐Turán theory.