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

摘要

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