关键词: 二部图, 平图, 正常多色染色

Abstract:

A proper k-coloring of a graph G is a vertex k-coloring such that adjacent vertices have different colors. A polychromatic k-coloring of a plane graph G is a vertex k-coloring such that every face meets all k colors. The degree of a face f of G is the number of vertices incident with f and is denoted by $g(f)$. Let $g(G)=\min\{g(f)|f\in F(G)\}$, where $F(G)$ is the face set of plane graph G. Obviously, if a plane graph G has a polychromatic k-coloring, then $k\leq g(G)$. In 2012, Horev et al. showed that every simple cubic bipartite plane graph is proper polychromatic 4-colorable (2012). In this paper, we extend the above result, and show that every subcubic bipartite plane graph G with $g(G)\geq 5$ has a proper polychromatic 4-coloring. The condition that $g(G)\geq 5$ is tight, because there exists (non-cubic) subcubic bipartite plane graph G which has $g(G)=4$ but has no proper polychromatic 4-coloring.

Key words: bipartite graph, plane graph, proper polychromatic coloring