Dense Graphs with Small Clique Number
Mathematics and Natural Sciences
We consider the structure of Kr-free graphs with large minimum degree, and show that such graphs with minimum degree δ>(2r-5)n/(2r-3) are homomorphic to the join Kr-3 ∨ H, where H is a triangle-free graph. In particular this allows us to generalize results from triangle-free graphs and show that Kr-free graphs with such a minimum degree have chromatic number at most r+1. We also consider the minimum-degree thresh-olds for related properties. (c) 2010 Wiley Periodicals, Inc. J Graph Theory 66: 319-331, 2011
Journal of Graph Theory
(2011). Dense Graphs with Small Clique Number. Journal of Graph Theory, 66(4), 319-331.
Available at: https://aquila.usm.edu/fac_pubs/485