Dense Graphs with Small Clique Number

Document Type

Article

Publication Date

4-1-2011

Department

Mathematics

School

Mathematics and Natural Sciences

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 thresh-olds for related properties. (c) 2010 Wiley Periodicals, Inc. J Graph Theory 66: 319-331, 2011

Publication Title

Journal of Graph Theory

Volume

66

Issue

4

First Page

319

Last Page

331

Link to Full Text

Find in your library

Share

COinS