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 $G$ such that $\delta (G)>|V(G)|/3$ is at most four. In fact, they showed the much stronger result that every maximal triangle-free graph $G$ 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 $G$ under the weaker assumption that for $m\in \{2,3,4\}$ every sequence of $3m$ vertices has a subsequence of length $m+1$ with a common neighbour. In forthcoming work this will be used to solve an old problem of Andrásfai in Ramsey-Turán theory.

arXiv comment34 figures