On the Chromatic Number of H-Free Graphs of Large Minimum Degree
Document Type
Article
Publication Date
9-1-2011
Department
Mathematics
School
Mathematics and Natural Sciences
Abstract
The problem of determining the chromatic number of H-free graphs has been well studied, with particular attention to K r -free graphs with large minimum degree. Recent progress has been made for triangle-free graphs on n vertices with minimum degree larger than n/3. In this paper, we determine the family of r-colorable graphs ℋr such that if H ∈ ℋr, there exists a constant C < (r − 2)/(r − 1) such that any H-free graph G on n vertices with δ(G) > Cn has chromatic number bounded above by a function dependent only on H and C. A value of C < (r − 2)/(r − 1) is given for every H ∈ ℋr, with particular attention to the case when χ(H) = 3.
Publication Title
Graphs and Combinatorics
Volume
27
Issue
5
First Page
741
Last Page
754
Recommended Citation
Lyle, J.
(2011). On the Chromatic Number of H-Free Graphs of Large Minimum Degree. Graphs and Combinatorics, 27(5), 741-754.
Available at: https://aquila.usm.edu/fac_pubs/21510