Kempe Revisited
In 1879 Kempe gave a procedure for 4-coloring an arbitrary planar graph (in the dual form of a planar map), but in 1890 Heawood found a flaw in the procedure. Specific examples indicate that Kempe's method can work for some vertex orderings and fails for others. The idea of combining randomness with Kempe's method has been considered by \textit{C. A. Morgenstern} and \textit{H. D. Shapiro} [Algorithmica 6, No. 6, 869-891 (1991; Zbl 0746.05060)]. In 1935 \textit{I. Kittell} [Bull. Am. Math. Soc. 41, 407-413 (1935; Zbl 0012.03501)] modified Kempe's method to produce an algorithm superior to the randomized Kempe procedure. The present note poses two questions: (1) Does every planar graph have some vertex labelling for which Kempe's coloring method succeeds in 4-coloring the graph? (2) Does the Kempe-Kittell algorithm always succeed?
- Mathematics and \texttt{Mathematica}
- How false is Kempe's proof of the four color theorem? II
- Kerr-Schild rides again
- Using Kempe exchanges to disentangle Kempe chains
- Klein vs Mehrtens: restoring the reputation of a great modern
- THE EXAMPLE THAT HEAWOOD SHOULD HAVE GIVEN
- scientific article; zbMATH DE number 2076921 (Why is no real title available?)
- Shewhart Revisited
- \(D\)-resolvability of vertices in planar graphs
- Hanoi revisited
- A catalog of facially complete graphs
This page was built for publication: Kempe Revisited
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4221600)