# 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