×

The four colour problem is not dead. (English) Zbl 0693.05027

Graph colourings, Proc. Conf., Milton Keynes/UK 1988, Pitman Res. Notes Math. Ser. 218, 37-44 (1990).
[For the entire collection see Zbl 0693.05025.]
In this paper some theorems equivalent to the four colour problem and related results are stated. They are expressed in terms of elements of order 2 or 3 in the group \(S_ 3\), line graphs of cubic maps, odd cuts and Tait colourings, parity-weighted graphs or bottlenecks in a non-Tait- colourable cubic graph. A conjecture which asserts that in any non-Tait colourable bridgeless cubic graph, the cuts of orders 3 and 5 form a bottleneck is proposed.
Reviewer: I.Tomescu

MSC:

05C15 Coloring of graphs and hypergraphs

Citations:

Zbl 0693.05025