On Brooks' Theorem for Sparse Graphs

Source abstract

Let G be a graph with maximum degree Δ( G ). In this paper we prove that if the girth g ( G ) of G is greater than 4 then its chromatic number, χ( G ), satisfies where o (l) goes to zero as Δ( G ) goes to infinity. (Our logarithms are base e .) More generally, we prove the same bound for the list-chromatic (or choice) number: provided g ( G ) < 4.