Dense graphs with small clique number |
| |
| Authors: | Wayne Goddard Jeremy Lyle |
| |
| Institution: | 1. School of Computing and Department of Mathematical Sciences, Clemson University Clemson, South Carolina;2. Department of Mathematics the University of Southern Mississippi Hattiesburg, Mississippi;3. Department of Mathematical Sciences Clemson University Clemson, South Carolina |
| |
| Abstract: | 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 thresholds for related properties. Copyright © 2010 John Wiley & Sons, Ltd. 66:319‐331, 2011 |
| |
| Keywords: | dense graphs clique coloring homomorphism minimum degree |
|
|
