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

LINEAR COLORING OF GRAPHS WITH SMALL MAXIMUM DEGREE

作　　者：彩春丽 易华[1] CAI Chun-li;YI Hua(School of Mathematics and Physics,Jinggangshan University,Ji’an Jiangxi 343009,China)

机构地区：[1]井冈山大学数理学院,江西吉安343009

出　　处：《井冈山大学学报（自然科学版）》2020年第5期5-9,共5页Journal of Jinggangshan University (Natural Science)

摘　　要：本文研究了最大度较小的图的线性着色问题。通过分析未着色顶点的邻近顶点的着色情况,扩充图的部分线性着色,利用数学归纳法证明了△(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.

关 键 词：最大度 线性着色 线性色数 

分 类 号：O157.5[理学—数学]