An improved bound on parity vertex colourings of outerplane graphs

作者：Wang Weifan^*; Finbow Stephen; Wang Ping

来源：Discrete Mathematics, 2012, 312(18): 2782-2787.

DOI：10.1016/j.disc.2012.04.009

• Parity vertex colouring
• Outerplane graph
• End face

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 chi(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 chi(p)(G) <= 9. In addition, we characterize the 2-connected outerplane graphs G with chi(p)(G) = 2 and those which are bipartite and have chi(p)(G) = 8.

• 出版日期2012-9-28
• 单位浙江师范大学