Dense graphs with bounded clique number

Stephan Brandt Freie Universität Berlin

The extremal graph characterization of Turán’s famous graph theorem shows that the K_{r}-free graphs of largest size and of largest minimum degree, respectively, have a very simple structure. If the requirements on the minimum degree are substantially lowered compared to the Turán bound, it turns out that much of the structure is preserved. This effect will be investigated for certain structural properties and for graph parameters like the independence number and the chromatic number.