返回Google圖書搜尋

Graph Minors and Hadwiger's Conjecture

出版	Ohio State University, 2005
URL	http://books.google.com.hk/books?id=DNPRjwEACAAJ&hl=&source=gbs_api

註釋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