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: Double-critical graphs and complete minors. | Double-critical graphs and complete minors Ken-ichi Kawarabayashi The National Institute of Informatics 2-1-2 Hitotsubashi Chiyoda-ku Tokyo 101-8430 Japan k_keniti@ Anders Sune Pedersen Bjarne Toft Dept. of Mathematics and Computer Science University of Southern Denmark Campusvej 55 5230 Odense M Denmark asp btoft @ Submitted Oct 14 2008 Accepted May 28 2010 Published Jun 7 2010 Mathematics Subject Classification 05C15 05C83 Abstract A connected k-chromatic graph G is double-critical if for all edges uv of G the graph G u v is k 2 -colourable. The only known double-critical k-chromatic graph is the complete k-graph Kk. The conjecture that there are no other double-critical graphs is a special case of a conjecture from 1966 due to Erdos and Lovasz. The conjecture has been verified for k at most 5. We prove for k 6 and k 7 that any non-complete double-critical k-chromatic graph is 6-connected and contains a complete k-graph as a minor. 1 Introduction A long-standing conjecture due to Erdos and Lovasz 5 states that the complete graphs are the only double-critical graphs. We refer to this conjecture as the Double-Critical Graph Conjecture. A more elaborate statement of the conjecture is given in Section 2 where several other fundamental concepts used in the present paper are defined. The Double-Critical Graph Conjecture is easily seen to be true for double-critical k-chromatic graphs with k at most 4. Mozhan 16 and Stiebitz 19 20 independently proved the conjecture to hold for k 5 but it still remains open for all integers k greater than 5. The Double-Critical Graph Conjecture is a special case of a more general conjecture the so-called Erdos-Lovasz Tihany Conjecture 5 which states that for any graph G with x G w G and any two integers a b 2 with a b x G 1 there is a partition A B of the vertex set V G such that x G A a and x G B b. The Erdos-Lovasz Tihany Conjecture holds for every pair a b G 2 2 2 3 2 4 3 3 3 4 3 5 see 3 16 19 20 . Kostochka and
