最大度为7且不含带弦5-圈的平面图是8-全可染的

Plane graphs with maximum degree 7 and without 5-cycles with chords are 8-totally-colorable

若能用k种颜色给图的顶点和边同时进行染色使得相邻或相关联的元素(顶点或边)染不同的色,则称这个图是k-全可染的.显然,给最大度为△的图进行全染色,至少要用△+1种不同的色.本文证明最大度为7且不含带弦5-圈的平面图是8-全可染的.这一结果进一步拓广了(△+1)-全可染图类.

Let G = （V, E） be a graph with the set of vertices V and the set of edges E. If one can use k colors to color the elements in V ∪ E such that any pair of adjacent or incident elements receive distinct colors, then G is said to be k-totally-colorable. Clearly, at least △＋ 1 colors are needed to color a graph totally, where A is the maximum degree of G. It is known that the plane graphs with maximum degree △ ≥ 8 and without 5-cycles with chords are （△ ＋ 1）-totally-colorable. In this paper, we prove that the plane graphs with maximum degree 7 and without 5-cycles with chords are 8-totally-colorable.