Algorithms Seminar

We characterize graphs with maximum degree Delta which are not k-colourable, when Delta is sufficiently large and k is close to Delta. In particular, we show that for (Delta+1-k)(Delta+2-k)< Delta, i.e. for k at least roughly Delta+1-sqrt{Delta}, such graphs must contain a small non-k-colourable subgraph, i.e. one whose size is bounded in terms of Delta. For (Delta+1-k)(Delta+2-k)= Delta, this does not hold, but non-k-colourable such graphs which do not contain such subgraphs have a simple structure. This is far from true when (Delta+1-k)(Delta+2-k)>Delta since in this case, Embden-Weinert, Hougardy and Kreuter proved that k-colourability is NP-complete even for Delta=O(1). (It is straightforward to see that our result implies that for $\Delta=O(1)$ and (Delta+1-k)(Delta+2-k)\leq Delta, k-colourability can be solved in polytime. In fact, we can solve it in linear time.) Our main result can be seen as a generalization of Brooks' Theorem, which states that when k=Delta, a graph of maximum degree Delta is not k-colourable iff it contains a (Delta+1)-clique. Here we show that for a wider range of k, and Delta sufficiently large, a non-k-colourable graph does not neccessarily contain a (k+1)-clique, but it contains something close: a small non-k-colourable subgraph.
Joint work with Bruce Reed..