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

作者：彩春丽^*; 易华

来源：井冈山大学学报(自然科学版), 2020, 41(05): 5-9.

• 最大度
• 线性着色
• 线性色数

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

• 单位
  数理学院; 井冈山大学