最大度等于5的图无循环着色

作者：张卫标; 杨瑞

来源：河南理工大学学报(自然科学版), 2019, 38(02): 149-152.

DOI：10.16186/j.cnki.1673-9787.2019.2.23

• 无循环着色
• 无循环色数
• 最大度

图G的无循环着色指图G的顶点着色,使图G的任何相邻顶点着不同色且在图G中不存在双色圈。本文为了研究最大度等于5的图G无循环着色,从图的结构出发,利用分类讨论法、穷尽染色法和换色技巧,证明了当图的最大度Δ(G)=5时,图G的无循环色数a(G)≤7。

• 单位
  河南理工大学; 商丘学院