Đang chuẩn bị liên kết để tải về tài liệu:
Báo cáo toán học: "Double-critical graphs and complete minors"

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@nii.ac.jp Anders Sune Pedersen Bjarne Toft Dept. of Mathematics and Computer Science University of Southern Denmark Campusvej 55 5230 Odense M Denmark asp btoft @imada.sdu.dk 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