外平面图的区间全染色

The Interval Total Colorings of Outerplane Graphs

图G的一个正常全染色是指一个映射φ:V(G)UE(G)→N,使得V(G)UE(G)中任意两个相邻的或相关联的元素染不同颜色。一个t-区间是指t个连续整数组成的集合。如果G的一个使用了颜色1,2,...,t的全染色使得G中任意顶点v以及与v关联的边使用了dG(v)+1种连续的颜色,其中dG(v)是G中顶点v的度,并且G中至少存在一个顶点或者一条边被染颜色i,i=1,2,...,t,则称此全染色为图G的一个区间全染色。在本文中,我们研究外平面图的区间全染色。

A total coloring of a graph G is a mapping φ:V(G)UE(G)→N, such that no adjacent vertices, edges, and no incidnet vertices and edges in V(G)UE(G) obtain the same color. A t-interval is a set of t consecutive integers. An interval total t-coloring of a graph G is a total coloring of with colors G 1,2,...,t such that at least one vertex or edge of G is colored by i, i=1,2,...,t, and the edges incident to each vertex v together with v are colored by dG(v)+1 consecutive colors, where dG(v) is the degree of the vertex v in G. In this paper, we study the interval total coloring of outerplane graphs.