Date of Award

Spring 5-2014

Degree Type

Masters Thesis

Degree Name

Master of Science (MS)

Department

Mathematics

Committee Chair

Jeremy Lyle

Committee Chair Department

Mathematics

Committee Member 2

John Perry

Committee Member 2 Department

Mathematics

Committee Member 3

Karen Kohl

Committee Member 3 Department

Mathematics

Abstract

The chromatic threshold of a class of graphs is the value θ such that any graph in this class with a minimum degree greater than θn has a bounded chromatic number. Several important results related to the chromatic threshold of triangle-free graphs have been reached in the last 13 years, culminating in a result by Brandt and Thomassé stating that any triangle-free graph on n vertices with minimum degree exceeding 1/3 n has chromatic number at most 4. In this paper, the researcher examines the class of triangle-free graphs that are additionally regular. The researcher finds that any triangle-free graph on n vertices that is regular of degree (1/4+a)n with a > 0 has chromatic number bounded by f (a), a function of a independent of the order of the graph n. After obtaining this result, the researcher generalizes this method to graphs that are free of larger cliques in order to limit the possible values of the chromatic threshold for regular Kr-free graphs.

Download

Share

COinS