图G的一个正常k-染色是G的一个k色点染色, 使得任两个相邻的顶点都异色。平图G的一个多色k-染色是G的一个k色点染色, 使得每个面出现k种不同的颜色。面f的度数是f上顶点的个数, 用$g(f)$来表示, 令$g(G)=\min\left\{g(f)|f\in F(G)\right\}$, 其中$F(G)$是平图G所有面的集合。显然, 若平图G存在多色k-染色, 则$k\leq g(G)$。Horev等人(2012)证明了3-正则二部简单平图是正常多色4-可染的。在本文中, 我们推广了上述结果, 证明了对于最大度是3的连通二部简单平图G, 若$g(G)\geq 5$, 则G是正常多色4-可染的。条件$g(G)\geq 5$是紧的, 因为存在$g(G)=4$最大度是3的连通二部简单平图G不能正常多色4-染色。

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.