外平面图的完备染色

The Entire Coloring of Outerplanar Graphs

设Ｖ（Ｇ）、Ｅ（Ｇ）和Ｆ（Ｇ）分别为平面图Ｇ的点集、边集和面集。Ｇ的完备色数Ｘｃ（Ｇ）是使得Ｖ（Ｇ）∪Ｅ（Ｇ）∪Ｆ（Ｇ）中相邻或相关联的元素间均染不同色的最少颜色数。本文证明了：对无割点的外平面图Ｇ，有Ｘｃ（Ｇ）≤ｍａｘ｛７，△（Ｇ）＋１｝，其中△（Ｇ）为Ｇ的最大度数。

Let G be a plane graph.V(G),E(G)and F(G)are the vertex set,the edge set and the face set.The entire chromatic number x_c(G)of G is the least number of colors assigned to V(G)∪E(G)∪F(G)such that no two adjacient or incident elements receive the same color.In the paper,we prove that x_c(G)≤max{7,△(G)+1} if G is a outerplanar graph with no cut vertices,where△(G)is the maximum degree of G.