An improved bound on parity vertex colourings of outerplane graphs

A parity vertex colouring of a 2-connected plane graph G is a proper vertex colouring such that for each face f and colour i, either zero or an odd number of vertices incident with f are coloured i. The parity chromatic number χp(G) of G is the smallest number of colours used in a parity vertex colo...

Full description

Saved in:
Bibliographic Details
Published in:Discrete mathematics 2012-09, Vol.312 (18), p.2782-2787
Main Authors: Wang, Weifan, Finbow, Stephen, Wang, Ping
Format: Article
Language:English
Subjects:
Color
Colour
Colouring
End face
Graphs
Mathematical analysis
Outerplane graph
Parity
Parity vertex colouring
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 parity vertex colouring of a 2-connected plane graph G is a proper vertex colouring such that for each face f and colour i, either zero or an odd number of vertices incident with f are coloured i. The parity chromatic number χp(G) of G is the smallest number of colours used in a parity vertex colouring of G. In this paper, we improve a result of Czap by showing that every 2-connected outerplane graph G, with two exceptions, has χp(G)≤9. In addition, we characterize the 2-connected outerplane graphs G with χp(G)=2 and those which are bipartite and have χp(G)=8.
ISSN:0012-365X
1872-681X
DOI:10.1016/j.disc.2012.04.009