供稿: 张卫标;杨瑞 | 时间: 2018-07-18 | 次数: |
作者:张卫标;杨瑞
作者单位:商丘学院计算机工程学院;河南理工大学数学与信息科学学院
摘要:为了研究Meredith图和系列平行图的无循环边着色问题,本文利用矩阵分析法、数学归纳法及其换色技巧,证明了若G_k是一个Meredith图,则有a’(G_k)=Δ(G_k),同时也证明了Δ(G)≥5的系列平行图的无循环边色数a’(G)≤Δ(G)+1。
关键词:系列平行图;Meredith图;矩阵分析;无循环边着色;
Abstract:In order to study acyclic edge coloring of Meredith graphs and series-parallel graphs, matrix analysis, mathematical induction as well as color-changing technique were employed in the study. The results show that for Meredith graphs, the equation a' (G) = Δ (Gk) is proved. Meanwhile, for series-parallel graphs of Δ (Gk) ≥5, a' (G) ≤ Δ (G) + 1 is also proved.
DOI:10.16186/j.cnki.1673-9787.2018.04.24
分类号:O157.5