AN ABSTRACT GENERALIZATION OF A MAP REDUCTION THEOREM OF BIRKHOFF

In 1913, George D, Birkhoff proved several theorems for planar maps, reducing the 4-colourability of maps containing certain configurations to the 4-colourability of smaller maps. One such result was that rings of size at most 4 are reducible. This was generalized by G. A. Dirac in 1960 to the abstract formulation that any contraction-critical k-chromatic graph not equal K-k is 5-connected. In the same spirit we generalize the reducibility of a 6-ring around 4 countries, each having 5 neighbours (sometimes called Birkhoffs diamond theorem) to the statement that in a contraction-critical k-chromatic graph not equal K-k no four vertices of degree k span a complete 4-graph with a missing edge. This is subsequently used to prove that the number of vertices of degree greater than or equal to k + 1 must be at least k - 4. It is remarked that such a result for all k with k - 4 replaced by ck - d, where c > 1, would imply Hadwiger's conjecture that there are no contraction-critical k-chromatic graphs not equal K-k for all k. (C) 1995 Academic Press, Inc.