Article ID Journal Published Year Pages File Type
4648147 Discrete Mathematics 2012 6 Pages PDF
Abstract

A facial parity edge colouring   of a connected bridgeless plane graph is such an edge colouring in which no two face-adjacent edges receive the same colour and, in addition, for each face ff and each colour cc, either no edge or an odd number of edges incident with ff is coloured with cc. Let χp′(G) denote the minimum number of colours used in such a colouring of GG. In this paper we prove that χp′(G)≤20 for any 2-edge-connected plane graph GG. In the case when GG is a 33-edge-connected plane graph the upper bound for this parameter is 1212. For GG being 44-edge-connected plane graph we have χp′(G)≤9. On the other hand we prove that some bridgeless plane graphs require at least 10 colours for such a colouring.

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, , , ,