The Effective Version of Brooks' Theorem

Publisher Website
Google Scholar
Abstract
One of the fundamental results on graph coloring is the following classical theorem of Brooks.BROOKS’ THEOREM. Suppose that k ≧ 3 and that G is a k-regular graph which does not induce a (k + 1)-clique. Then G is k-colorable.Brooks proved his theorem in [1]; several more recent proofs have appeared in [3], [4] and [5]. All the proofs of this theorem have the common feature of applying only to finite graphs; the transition to infinite graphs can be accomplished by a very standard implementation of the Compactness Theorem (or some other equally noneffective device such as the theorem of deBruijn and Erdös [2] asserting that a graph is k-colorable if and only if each of its finite subgraphs is). Thus, it is not immediately apparent that an effective version of Brooks’ Theorem exists. It is our purpose to show, however, that the effective analogue of Brooks' Theorem is indeed true.

This publication has 0 references indexed in Scilit: