On Complete Graph Minors

In this thesis,we study the graph minors.More precisely,we concentrate on the famous Hadwiger conjecture as well as its related Woodall conjecture.The graph minor theory is a project with long history,which can be traced back to the days of the Four Color Conjecture.In this field,the Hadwiger conjecture has caught much attention.Because Robertson and Seymour developed a series of minor theory,we have some useful tools in studying graph minors.However,when it comes to seeking for the relation of graph minors and other graph parameters,where Hadwiger asked for chromatic number and Woodall thought of stability number,recent results are still not so satisfactory.These two conjectures are still widely open.In this thesis,I have studied most of the latest literature,and have a thorough comprehension of recent work and clear understanding of the barriers blocking the problem.I have made some improvements on earlier results of Fox and B¨ohme et al.,combining the latest research work.The main work of this thesis,is a result on the Woodall conjecture,which shows a relation of graph minors and stability numbers.We denote the stability number,the Hadwiger number and the number of vertices of a graph by ?,h,and n,respectively.Inspired by the Hadwiger conjecture,Woodall came up with the conjecture that the inequality?h ? n holds.The best current results are as follows:Kawarabayashi et al.proved that(2?-2)h ? n holds for ? ? 3;and Wood proved(2?-1)(2h-5)? 2n-5,given the condition of h ? 5.I have made an improvement of both of the results.In details,I have proved inequality(?-1)(2h-5)? n-5 is true for graphs with ? ? 3 and h ? 5.