Skip to Main Content
 

Global Search Box

 
 
 
 

ETD Abstract Container

Abstract Header

Graph minors and Hadwiger's conjecture

Micu, Eliade Mihai

Abstract Details

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

Citations

  • Micu, E. M. (2005). Graph minors and Hadwiger's conjecture [Doctoral dissertation, Ohio State University]. OhioLINK Electronic Theses and Dissertations Center. http://rave.ohiolink.edu/etdc/view?acc_num=osu1123259686

    APA Style (7th edition)

  • Micu, Eliade. Graph minors and Hadwiger's conjecture. 2005. Ohio State University, Doctoral dissertation. OhioLINK Electronic Theses and Dissertations Center, http://rave.ohiolink.edu/etdc/view?acc_num=osu1123259686.

    MLA Style (8th edition)

  • Micu, Eliade. "Graph minors and Hadwiger's conjecture." Doctoral dissertation, Ohio State University, 2005. http://rave.ohiolink.edu/etdc/view?acc_num=osu1123259686

    Chicago Manual of Style (17th edition)