On Brooks' Theorem for Sparse Graphs

Author:
  • JKJeong Han Kim
    Jeong Han Kim

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.

This publication has 16 references indexed in Scilit: