5 - Beyond the Four Colour theorem

Summary

Prologue

“The Four Colour Problem has been solved by K. Appel, W. Haken and J. Koch. But what about the other mathematicians who have been working on the problem? I imagine one of them outgribing in despair, crying ‘What shall I do now?’ To which the proper answer is ‘Be of good cheer. You can continue in the same general line of research. You can study the Hajós and Hadwiger Conjectures. You can attack the problem of 5-flows and you can try to classify the tangential 2-blocks.’”

In this optimistic vein, Tutte [wT 78], rallied possibly disheartened ‘Mapmen’. We have already given some space to Hajos and to Hadwiger in Section 2.5. Now we turn our attention to the last two problems mentioned by Tutte above, namely the problem of 5-flows and the classification of tangential 2-blocks.

Some real progress has been made, not only on the questions themselves in [bD76], [bD 81], [fJ 76] and [pS 81b], but also on the intimate relationship between them - [dW 79], [dW 80], [pS 81a] .

In fact P.D. Seymour [pS 81b] has shown that every bridgeless graph has a nowhere-zero 6-flow.

Flows

Let G be a finite pseudograph. Orient G by putting arrows on each edge e ∈ EG, so that one end of e is distinguished as the tail t(e) of e and the other as the head h(e) of e. Hence t(e) = h(e) if and only if e is a loop.