06081324

j

06081324 Wang, Weifan Finbow, Stephen Wang, Ping An improved bound on parity vertex colourings of outerplane graphs. Discrete Math. 312, No. 18, 2782-2787 (2012). 2012 Elsevier Science B.V. (North-Holland), Amsterdam EN parity vertex colouring outerplane graph end face

doi:10.1016/j.disc.2012.04.009

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 $\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)\leq 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$.