Premium
Dense graphs with small clique number
Author(s) -
Goddard Wayne,
Lyle Jeremy
Publication year - 2011
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.20505
Subject(s) - combinatorics , mathematics , degree (music) , clique sum , discrete mathematics , chordal graph , graph , split graph , metric dimension , 1 planar graph , physics , acoustics
We consider the structure of K r ‐free graphs with large minimum degree, and show that such graphs with minimum degree δ>(2 r − 5) n /(2 r − 3) are homomorphic to the join K r − 3 ∨ H , where H is a triangle‐free graph. In particular this allows us to generalize results from triangle‐free graphs and show that K r ‐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
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom