Simultaneously Colouring the Edges and Faces of Plane Graphs

Journal article published in 1997 by Adrian O. Waller

Full text: Download

Publisher: Elsevier

Preprint: archiving allowed. Upload

Postprint: archiving allowed. Upload

Published version: archiving forbidden. Upload

Policy details (opens in a new window). Data provided by SHERPA/RoMEO
In a simultaneous colouring of the edges and faces of a plane graph we colour edges and faces so that every two adjacent or incident pair of them receive different colours. In this paper we prove a conjecture of Mel'nikov which states that for this colouring every plane graph can be coloured withΔ+3 colours, whereΔis the maximum degree of a vertex in the graph.