Facial parity edge colouring of plane pseudographs

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 f and each colour c, either no edge or an odd number of edges incident with f is coloured with c. Let χp′(G) deno...

Full description

Saved in:
Bibliographic Details
Published in:Discrete mathematics 2012-09, Vol.312 (17), p.2735-2740
Main Authors: Czap, Július, Jendroľ, Stanislav, Kardoš, František, Soták, Roman
Format: Article
Language:English
Subjects:
Color
Colour
Colouring
Computer Science
Discrete Mathematics
Edge colouring
Facial
Facial walk
Graphs
Mathematical analysis
Parity
Plane graph
Planes
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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 f and each colour c, either no edge or an odd number of edges incident with f is coloured with c. Let χp′(G) denote the minimum number of colours used in such a colouring of G. In this paper we prove that χp′(G)≤20 for any 2-edge-connected plane graph G. In the case when G is a 3-edge-connected plane graph the upper bound for this parameter is 12. For G being 4-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.
ISSN:0012-365X
1872-681X
DOI:10.1016/j.disc.2012.03.036