>> 自然科学版期刊 >> 2018年04期 >> 正文
两类图的无循环边着色
供稿: 张卫标;杨瑞 时间: 2018-07-18 次数:

作者:张卫标;杨瑞

作者单位:商丘学院计算机工程学院河南理工大学数学与信息科学学院

摘要:为了研究Meredith图和系列平行图的无循环边着色问题,本文利用矩阵分析法、数学归纳法及其换色技巧,证明了若G_k是一个Meredith图,则有a’(G_k)=Δ(G_k),同时也证明了Δ(G)≥5的系列平行图的无循环边色数a’(G)≤Δ(G)+1。

基金:国家自然科学基金资助项目(11626089);

关键词:系列平行图;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

最近更新