In 1943, Hadwiger conjectured that any k-chromatic graph contains a Kk-minor. Reed and Seymour proved that the conjecture is true for line graphs. We prove that the same holds for complements of line graphs. This thesis consists of two chapters.In chapter 1, we presents the background and give some necessary terminology and nota-tions.Chapter 2 is the main part of the thesis and is divided into three sections. Section 1 and section 2, we give some results on chromatic number, connected matching, Hadwiger number of complements of line graphs. In the third section, we give the proof of our main theorem.
|