Chromatic Thresholds of Regular Graphs with Small Cliques

<p>The chromatic threshold of a class of graphs is the value <em>θ</em> such that any graph in this class with a minimum degree greater than <em>θn</em> 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 <em>n</em> vertices with minimum degree exceeding 1/3 <em>n</em> 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 <strong>(</strong>1/4<strong>+</strong><em>a</em><strong>)</strong><em>n</em> with <em>a</em> > 0 has chromatic number bounded by <em>f <strong>(</strong>a<strong>)</strong></em>, a function of a independent of the order of the graph <em>n</em>. 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 <em>Kr</em>-free graphs.</p>

Name thesis:degree_name

Master of Science (MS)

Level thesis:degree_level

Masters Thesis

Discipline thesis:degree_discipline

Mathematics

Year dc:date.available

2014

Author dc:creator

• O'Rourke, Jonathan Lyons

Contributors dc:contributor

• Jeremy Lyle
• John Perry
• Karen Kohl

• chromatic number
• chromatic threshold
• graph theory
• regular graphs

Repository record dc:identifier

https://aquila.usm.edu/masters_theses/27

OAI identifier oai:identifier

oai:aquila.usm.edu:masters_theses-1020