Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
9515949 | Journal of Combinatorial Theory, Series B | 2005 | 13 Pages |
Abstract
Every graph G of maximum degree Î is (Î+1)-colourable and a classical theorem of Brooks states that G is not Î-colourable iff G has a (Î+1)-clique or Î=2 and G has an odd cycle. Reed extended Brooks' Theorem by showing that if Î(G)⩾1014 then G is not (Î-1)-colourable iff G contains a Î-clique. We extend Reed's characterization of (Î-1)-colourable graphs and characterize (Î-2), (Î-3), (Î-4) and (Î-5)-colourable graphs, for sufficiently large Î, and prove a general structure for graphs with Ï close to Î. We give a linear time algorithm to check the (Î-k)-colourability of a graph, for sufficiently large Î and any constant k.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Babak Farzad, Michael Molloy, Bruce Reed,