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.
","abstract_html":"<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>","abstract_has_math":false,"creators":["O'Rourke, Jonathan Lyons"],"institution":null,"degree_name":"Master of Science (MS)","degree_level":"Masters Thesis","degree_discipline":"Mathematics","degree_department":null,"school":null,"contributors":["Jeremy Lyle","John Perry","Karen Kohl"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2014,"date_issued":"2014-05-01T07:00:00Z","date_published":"2014-05-01T07:00:00Z","updated_at":"2026-07-24T05:44:27Z","subjects":["chromatic number","chromatic threshold","graph theory","regular graphs"],"languages":[],"rights":[],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"https://aquila.usm.edu/masters_theses/27","outbound_label":"Repository record","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Jeremy Lyle","John Perry","Karen Kohl"]},{"key":"dc:creator","label":"Author","values":["O'Rourke, Jonathan Lyons"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.available","label":"Dc Date Available","values":["2014-06-09T07:00:00Z"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Mathematics"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Masters Thesis"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Master of Science (MS)"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["chromatic number","chromatic threshold","graph theory","regular graphs"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["https://aquila.usm.edu/masters_theses/27"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description.abstract","label":"Abstract","values":["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.
"]},{"key":"dc:title","label":"Title","values":["Chromatic Thresholds of Regular Graphs with Small Cliques"]}]}],"canonical_facts":{"dc:contributor":["Jeremy Lyle","John Perry","Karen Kohl"],"dc:creator":["O'Rourke, Jonathan Lyons"],"dc:date.available":["2014-06-09T07:00:00Z"],"dc:description.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.
"],"dc:identifier":["https://aquila.usm.edu/masters_theses/27"],"dc:subject":["chromatic number","chromatic threshold","graph theory","regular graphs"],"dc:title":["Chromatic Thresholds of Regular Graphs with Small Cliques"],"thesis:degree_discipline":["Mathematics"],"thesis:degree_level":["Masters Thesis"],"thesis:degree_name":["Master of Science (MS)"]},"updated_at":"2026-07-24T05:44:27Z"}