A strengthening of Brooks' Theorem for line graphs (Q553999)

Summary: We prove that if \(G\) is the line graph of a multigraph, then the chromatic number \(\chi(G)\) of \(G\) is at most \(\max\{\omega(G), {7\Delta(G)+ 10\over 8}\}\), where \(\omega(G)\) and \(\Delta(G)\) 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 \(\chi(G)\geq\Delta(G)\geq 9\), then \(G\) contains a clique on \(\Delta(G)\) vertices. Thus the Borodin-Kostochka conjecture holds for line graphs of multigraphs.