Skip to Main Content
Frequently Asked Questions
Submit an ETD
Global Search Box
Need Help?
Keyword Search
Participating Institutions
Advanced Search
School Logo
Files
File List
osu1123259686.pdf (380.94 KB)
ETD Abstract Container
Abstract Header
Graph minors and Hadwiger's conjecture
Author Info
Micu, Eliade Mihai
Permalink:
http://rave.ohiolink.edu/etdc/view?acc_num=osu1123259686
Abstract Details
Year and Degree
2005, Doctor of Philosophy, Ohio State University, Mathematics.
Abstract
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.
Committee
Neil Robertson (Advisor)
Pages
80 p.
Subject Headings
Mathematics
Keywords
Graph minors
;
Hadwiger's conjecture
Recommended Citations
Refworks
EndNote
RIS
Mendeley
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)
Abstract Footer
Document number:
osu1123259686
Download Count:
3,490
Copyright Info
© 2005, all rights reserved.
This open access ETD is published by The Ohio State University and OhioLINK.