Graph minors and Hadwiger's conjecture

One of the central open problems in Graph Theory is Hadwiger's Conjecture, which states that any graph with no Kk+1-minor 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 C4 or an induced C5, 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.