2024/06/15 by Tomasz Łuczak, Łuczak, Tomasz, Joanna Polcyn +3 · 1 citation
Mathematics · Computer Science · #Advanced Algebra and Geometry #Matrix Theory and Algorithms
paper · pdf · doi:10.48550/arxiv.2406.10745
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 δ(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∈\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.