Any 7-Chromatic Graphs Has K 7 Or K 4,4 As A Minor

In 1943, Hadwiger made the conjecture that every k-chromatic graph has a K _k -minor. This conjecture is, perhaps, the most interesting conjecture of all graph theory. It is well known that the case k=5 is equivalent to the Four Colour Theorem, as proved by Wagner [39] in 1937. About 60 years later, Robertson, Seymour and Thomas [29] proved that the case k=6 is also equivalent to the Four Colour Theorem. So far, the cases k7 are still open and we have little hope to verify even the case k=7 up to now. In fact, there are only a few theorems concerning 7-chromatic graphs, e. g. [17].In this paper, we prove the deep result stated in the title, without using the Four Colour Theorem [1,2,28]. This result verifies the first unsettled case m=6 of the (m,1)-Minor Conjecture which is a weaker form of Hadwigers Conjecture and a special case of a more general conjecture of Chartrand et al. [8] in 1971 and Woodall [42] in 1990.The proof is somewhat long and uses earlier deep results and methods of Jørgensen [20], Mader [23], and Robertson, Seymour and Thomas [29].* Research partly supported by the Japan Society for the Promotion of Science for Young Scientists. Research partly supported by the Danish Natural Science Research Council.Dedicated to Professor Mike Plummer on the occasion of his sixty-fifth birthday.