Honors Theses
Date of Award
2009
Document Type
Undergraduate Thesis
Department
Mathematics
First Advisor
Laura Sheppardson
Relational Format
Dissertation/Thesis
Abstract
Graph theory is the study of graphs that represent a specific relation between pairs of objects from a collection. The objects are represented by vertices that are connected by edges defining the existence of such relation ship. A crucial result in graph theory, the Four Color Theorem, was first proposed in 1852 by Francis Guthrie but was not proven until 1976 by Ken neth Appel and Wolfgang Haken. The Four Color Theorem says that any graph on a plane is four colorable. Then in 1943 Hugo Hadwiger presented generalization of the Four Color Theorem which is still an important and unsolved proposition in graph theory today. He conjectured that if a graph G is fc-chromatic then it must contain a complete minor of size k. By reading original papers and essays, I sought an understanding of graph theory and Hadwiger’s Conjecture before researching the character istics of specific graphs such as the Mycielski Construction and the Kneser Graph. I found that for both the Mycielski construction and the Kneser graph Hadwiger’s conjecture holds. They both contain large complete mi nors that are the same size as the chromatic number of the graph. That is if the chromatic number of the graph is k then there exists a complete minor of size k. Hence, although Hadwiger’s conjecture has still not been proven to be true, both the Kneser graph and Mycielski construction proved to be good examples of the conjecture. Hadwiger’s conjecture is interesting because the connection between col oring and minors is an important area of study in graph theory. It could allow for a more complete characterization of graphs.
Recommended Citation
Nicholas, Anne Marie, "Hadwiger's Conjecture applied to Mycielski and Kneser Graphs" (2009). Honors Theses. 2079.
https://egrove.olemiss.edu/hon_thesis/2079
Accessibility Status
Searchable text