最大度较小的图的线性着色

LINEAR COLORING OF GRAPHS WITH SMALL MAXIMUM DEGREE

本文研究了最大度较小的图的线性着色问题。通过分析未着色顶点的邻近顶点的着色情况,扩充图的部分线性着色,利用数学归纳法证明了△(G)≤4的非4正则图G的线性色数有lc(G)≤7和△(G)≤5的非5正则图G的线性色数有lc(G)≤13。

we studied the problem of linear coloring of graphs with small maximum degree.By analyzing the coloring of the vertices with distance at most 2 from the uncolored vertex,extending the partial linear coloring of graph to the whole graph,and usingmathematical induction,we proved that lc(G) ≤7 if Gis not4-regular graph with Δ(G) ≤4,and lc(G) ≤13 if Gis not5-regular graph with Δ(G) ≤5.