Problem 4.6: Brooks' Theorem for Triangle-free Graphs

A proof of A. Johansson's bound for triangle-free graphs
(G) c(G) / log (G),
where c > 0 is a constant, is available in

A. Johansson, Some results on colourings of graphs, Doctoral Thesis, Department of Mathematics, University of Umeå, 1994. (ISBN 91-7174-974-8)

It should also be noted that Johansson obtained this bound as a corollary of the same upper bound proved for the list-chromatic number of triangle-free graphs.

Tommy R. Jensen, September 4 1998.

Back to Overview menu
Back to Graph Coloring Problems homepage

Last modified September 4, 1998 Tommy R. Jensen