Search ETDs:
Graph minors and Hadwiger's conjecture
Micu, Eliade Mihai

2005, Doctor of Philosophy, Ohio State University, Mathematics.
One of the central open problems in Graph Theory is Hadwiger's Conjecture, which states that any graph with no clique minor of size k+1 is k-colorable. Restated, the conjecture asserts that the clique-minor number is always an upper bound for the chromatic number. In this paper we study various connections between these invariants. We start by providing the definitions and basic results needed later on, together with a new result about coloring "almost all" the vertices of a graph. In the second chapter, we focus on graphs with stability number equal to two, proving that if such a graph does not contain an induced cycle of length 4 or 5, it satisfies Hadwiger's Conjecture. The next chapter is dedicated to proving a result which is implied by the conjecture, i.e. an inequality linking the clique-minor numbers of a graph and its complement. We conclude the paper with a result about the embedding of any finite graph in Euclidean 3-space such that all its edges are straight line segments of integer length.
Neil Robertson (Advisor)
80 p.

Recommended Citations

Hide/Show APA Citation

Micu, E. (2005). Graph minors and Hadwiger's conjecture. (Electronic Thesis or Dissertation). Retrieved from https://etd.ohiolink.edu/

Hide/Show MLA Citation

Micu, Eliade. "Graph minors and Hadwiger's conjecture." Electronic Thesis or Dissertation. Ohio State University, 2005. OhioLINK Electronic Theses and Dissertations Center. 26 Sep 2017.

Hide/Show Chicago Citation

Micu, Eliade "Graph minors and Hadwiger's conjecture." Electronic Thesis or Dissertation. Ohio State University, 2005. https://etd.ohiolink.edu/

Files

osu1123259686.pdf (380.94 KB) View|Download