tailieunhanh - Báo cáo toán học: "Complete and almost complete minors in double-critical 8-chromatic graphs"

Tuyển tập các báo cáo nghiên cứu khoa học ngành toán học tạp chí Department of Mathematic dành cho các bạn yêu thích môn toán học đề tài: Complete and almost complete minors in double-critical 8-chromatic graphs. | Complete and almost complete minors in double-critical 8-chromatic graphs Anders Sune Pedersen Dept. of Mathematics and Computer Science University of Southern Denmark Campusvej 55 5230 Odense M Denmark asp@ Submitted Jul 30 2010 Accepted Mar 18 2011 Published Apr 7 2011 Mathematics Subject Classification 05C15 05C83 Abstract A connected k-chromatic graph G is said to be double-critical if for all edges uv of G the graph G u v is k 2 -colourable. A longstanding conjecture of Erdos and Lovasz states that the complete graphs are the only double-critical graphs. Kawarabayashi Pedersen and Toft Electron. J. Combin. 17 1 Research Paper 87 2010 proved that every double-critical k-chromatic graph with k 7 contains a Kk minor. It remains unknown whether an arbitrary double-critical 8-chromatic graph contains a K8 minor but in this paper we prove that any double-critical 8-chromatic contains a minor isomorphic to K8 with at most one edge missing. In addition we observe that any double-critical 8-chromatic graph with minimum degree different from 10 and 11 contains a K8 minor. 1 Introduction motivation and main results At the very center of the theory of graph colouring is Hadwiger s Conjecture which dates back to 1942. It states that every k-chromatic graph1 contains a Kk minor. Conjecture Hadwiger 10 . If G is a k-chromatic graph then G contains a Kk minor. Hadwiger 10 showed that the conjecture holds for k 4 the case k 4 being the first non-trivial instance of the conjecture. Later several short and elegant proofs for the case k 4 were found see for instance 30 . The case k 5 was studied independently by Wagner 31 who proved that the case k 5 is equivalent to the Four Colour Problem. In 1 All graphs considered in this paper are undirected simple and finite. The reader is referred to Section 2 for basic graph-theoretic terminology and notation. THE ELECTRONIC JOURNAL OF COMBINATORICS 18 2011 P80 1 the early 1960s Dirac 7 and Wagner 32 independently proved .