外平面图的有界染色

BONUNDED COLORINGS OF OUTERPLANAR GRAPHS

图G的k-有界染色是图G的一个最多有k个顶点染同一种颜色的顶点染色．图 G的k-有界染色数Xk(G)是指对G进行k-有界染色用的最少颜色数．本文给出了n个顶点的外平面图能用[n/k]种颜色k-有界染色的一些充分条件．

A k-bounded vertex coloring of a graph G is a proper vertex coloring in which at most k vertices are colored with the same color. The k-bounded chromatic number xk（G） of a graph G is the smallest number of colors p such that G admits a k-bounded coloring with p colors. In this paper, we provide some sufficient conditions for outerplanar graphs with n vertices to be k-bounded colored with [n/k] colors.