TAILIEUCHUNG - Báo cáo toán học: "A strengthening of Brooks’ Theorem for line 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: A strengthening of Brooks’ Theorem for line graphs. | A strengthening of Brooks Theorem for line graphs Landon Rabern 314 Euclid Way Boulder CO . Submitted Feb 10 2010 Accepted Jun 20 2011 Published Jul 15 2011 Mathematics Subject Classification 05C15 Abstract We prove that if G is the line graph of a multigraph then the chromatic number A c1í r is il r ỴỴI I l ỴỴI V J I 1 r a 10 1 I. Il Ill ll I I i l I I I il rí I II í I I I I I I í I yx G of GJ is at most max Í c Gj 8 c Where c Gj and AA Gj are the clique number and the maximum degree of G respectively. Thus Brooks Theorem holds for line graphs of multigraphs in much stronger form. Using similar methods we then prove that if G is the line graph of a multigraph with x G A G 9 then G contains a clique on A G vertices. Thus the Borodin-Kostochka Conjecture holds for line graphs of multigraphs. 1 Introduction We define nonstandard notation when it is first used. For standard notation and terminology see 2 . The clique number of a graph is a trivial lower bound on the chromatic number. Brooks Theorem gives a sufficient condition for this lower bound to be achieved. Theorem 1 Brooks 4 . If G is a graph with A G 3 and x G A G 1 then w G x G - We give a much weaker condition for the lower bound to be achieved when G is the line graph of a multigraph. Theorem 2. If G is the line graph of a multigraph with x G 7A 8 10 then w G x G . Combining this with an upper bound of Molloy and Reed 16 on the fractional chromatic number and partial results on the Goldberg Conjecture 8 yields yet another proof of the following result see 14 for the original proof and 17 for further remarks and a different proof . Theorem 3 King Reed and Vetta 14 . If G is the line graph of a multigraph then x G U G A G 1 2 THE ELECTRONIC JOURNAL OF COMBINATORICS 18 2011 p145 1 0 G A G 1 2 holds for all graphs G. Reed 18 conjectures that the bound x G For further information about Reed s conjecture see King s thesis 11 and King and Reed s proof of the conjecture for .

• Báo cáo khoa học
• báo cáo của tạp chí Department of Mathematic
• tài liệu báo cáo nghiên cứu khoa học
• cách trình bày báo cáo
• kiến thức toán học
• báo cáo toán học