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 .
