供稿: 张卫标;杨瑞 | 时间: 2019-04-16 | 次数: |
作者:张卫标;杨瑞
作者单位:重庆大学数学与统计学院;商丘学院计算机工程学院;河南理工大学数学与信息科学学院
摘要:图G的无循环着色指图G的顶点着色,使图G的任何相邻顶点着不同色且在图G中不存在双色圈。本文为了研究最大度等于5的图G无循环着色,从图的结构出发,利用分类讨论法、穷尽染色法和换色技巧,证明了当图的最大度Δ(G)=5时,图G的无循环色数a(G)≤7。
基金:国家自然科学基金资助项目(11626089);河南省高等学校重点研究项目(18B110018);
DOI:10.16186/j.cnki.1673-9787.2019.2.23
分类号:O157.5
Abstract:An acyclic coloring of a graph is a proper vertex coloring and no bichromatic cycles. In order to study the acyclic coloring of graphs with maximum degree of 5. classified coloring, exhaustion coloring and the color-changing technique of structure of graphs were discussed. The results proved that when graph of maximum degree is 5, its acyclic chromatic number is less than 7.