Kempe Revisited

From MaRDI portal





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?











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)