Name
Abstract | ||
|---|---|---|
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 ≠ 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 Birkhoff′s diamond theorem) to the statement that in a contraction-critical k -chromatic graph ≠ 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 ≥ 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 ≠ K k for all k . |
Year | DOI | Venue |
|---|---|---|
1995 | 10.1006/jctb.1995.1049 | J. Comb. Theory, Ser. B |
Keywords | DocType | Volume |
abstract generalization,map reduction theorem | Journal | 65 |
Issue | ISSN | Citations |
2 | Journal of Combinatorial Theory, Series B | 1 |
PageRank | References | Authors |
0.48 | 2 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Michael Stiebitz | 1 | 207 | 30.08 |
| Bjarne Toft | 2 | 195 | 51.79 |