The Structure of Dense Graphs with Small Clique Number

Jeremy Lyle

ABSTRACT: In this talk, we prove a general structural result about partitioning dense graphs which contain no clique of size r, which in particular allows us to extend results from triangle-free graphs and show that dense graphs of size n which contain no clique of size r and have minimum degree larger than (2r-5)/(2r-3)n have chromatic number at most r+1. Lastly, we will discuss other uses of this result, in particular as it applies to the binding number of a graph.