On the Chromatic Number of H-Free Graphs of Large Minimum Degree |
| |
Authors: | Jeremy Lyle |
| |
Affiliation: | 1. Department of Mathematics, The University of Southern Mississippi, Hattiesburg, MS, USA
|
| |
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 Hr{mathcal{H}_r}, such that if H ? Hr{H in mathcal{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 ? Hr{H in mathcal{H}_r}, with particular attention to the case when χ(H) = 3. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|