On simultaneous edge-face colorings of plane graphs (Q1272182)

It is proved that the edges and faces of a plane graph may be simultaneously colored with at most \(\Delta +3\) colors, so that adjacent and incident elements receive different colors, where \(\Delta\) is the maximum degree of the graph. The result is tight, since an odd cycle requires that many colors. This settles a conjecture of Melnikov. It is also shown that if \(\Delta \geq 8\) then it is sufficient to use \(\Delta +2\) colors. The proof uses the four color theorem and Vizing's theorem.