A new proof of Melnikov's conjecture on the edge-face coloring of plane graphs (Q1613521)

In 1975 Melnikov conjectured that the edges and faces of each plane graph \(G\) can be colored with \(\Delta(G)+3\) colors so that any two adjacent or incident elements receive different colors, where \(\Delta(G)\) is the maximum degree of \(G\). Two similar, yet independent, proofs of this conjecture have been published recently by \textit{A. O. Waller} [J. Comb. Theory, Ser. B 69, 219-221 (1997; Zbl 0867.05023)] and \textit{D. P. Sanders} and \textit{X. Zhao} [Combinatorica 17, 441-445 (1997; Zbl 0902.05024)]. Both proofs made use of the four-color theorem. The authors of the paper under review present a new proof of Melnikov's conjecture. Their proof renders the extraordinary difficult four-color theorem dispensable in this context. Finally, they suppose that any plane bipartite graph \(G\) with \(\Delta(G)\geq 3\) is \(\Delta(G)+1\) edge-face colorable.