ON SIMULTANEOUS EDGE-FACE COLORINGS OF PLANE GRAPHS

This article proves a conjecture of Melnikov that the edges and faces of a plane graph may be simultaneously colored with at most Delta+3 co lors, so that adjacent and incident elements receive different colors, where Delta is the maximum degree of the graph. An odd cycle requires Delta+3 colors.