Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4656830 | Journal of Combinatorial Theory, Series B | 2014 | 62 Pages |
Abstract
We consider the chromatic number of graphs with maximum degree Δ. For sufficiently large Δ, we determine the precise values of k for which the barrier to (Δ+1−k)(Δ+1−k)-colourability must be a local condition, i.e. a small subgraph. We also show that for Δ constant and sufficiently large, (Δ+1−k)(Δ+1−k)-colourability is either NP-complete or can be solved in linear time, and we determine precisely which values of k correspond to each case.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Michael Molloy, Bruce Reed,