tailieunhanh - Báo cáo toán học: "The Borodin-Kostochka conjecture for graphs containing a doubly critical edge"

Tuyển tập các báo cáo nghiên cứu khoa học về toán học trên tạp chí toán học quốc tế đề tài: The Borodin-Kostochka conjecture for graphs containing a doubly critical edge. | The Borodin-Kostochka conjecture for graphs containing a doubly critical edge Landon Rabern Submitted Jul 23 2007 Accepted Oct 14 2007 Published Oct 24 2007 Mathematics Subject Classification 05C15 Abstract We prove that if G is a graph containing a doubly-critical edge and satisfying X A 6 then G contains a Ka. 1 Introduction Way back in 1977 Borodin and Kostochka made the following conjecture see 1 . Conjecture. Every graph satisfying X A 9 contains a Ka. Examples exist showing that the A 9 condition is necessary . for the A 8 case take a 5-cycle and expand each vertex to a triangle . In 1999 Reed proved the conjecture for A 1014 see 3 . Definition 1. Let G be a graph. An edge ab 2 G is doubly critical just in case x G r a bg X G - 2. We prove the following. Theorem A. Let G be a graph containing a doubly critical edge. If G satisfies X A 6 then G contains a Ka. To see that this result is tight consider the following graph. Put A 1 2g B 3 4 5g and C 6 7 8 9g. Let G be the graph having V G AUBuC with A and C complete B empty and the additional edges 13 14 15 23 24 25 64 65 73 75 83 84 93 94. It is easily checked that G satisfies X A 5 and 4. Also G contains a doubly critical edge since removing both vertices 8 and 9 leaves a 3-chromatic graph. A counterexample with X A 4 can be made by removing vertices 1 and 9 from G. The theorem holds trivially for A 3 since the only triangle-free graph containing a doubly critical edge is k2. THE ELECTRONIC JOURNAL OF COMBINATORICS 14 2007 N22 1 We briefly mention a related conjecture of Lovasz. He conjectures that the stronger condition that every edge of a connected graph G is doubly critical implies that G is complete see 1 . Stiebitz has shown that this conjecture holds for graphs with chromatic number at most 5 see 4 . 2 The Lonely Path Lemma We reproduce the relevant definitions and lemmas from 2 . Definition 2. Let C I1 . Im be a coloring of a graph G. If there exists j k such that v 2 Ij w 2 .