系列平行图和Meredith图的无循环边着色  

Acyclic edge coloring of series-parallel graphs and Meredith graphs

作　　者：张卫标[1] 谢德政[2] ZHANG Weibiao;XIE Dezheng(College of Computer Science and Technology, Shangqiu University, Shangqiu 476000, Henan Province, China;College of Mathematics and Statistics, Chongqing University, Chongqing 400044, China)

机构地区：[1]商丘学院计算机工程学院,河南商丘476000 [2]重庆大学数学与统计学院,重庆400044

出　　处：《天津师范大学学报（自然科学版）》2018年第2期7-9,共3页Journal of Tianjin Normal University：Natural Science Edition

基　　金：国家自然科学基金资助项目(11601128);河南省高等学校重点科研资助项目(18B110018)

摘　　要：利用数学归纳法,通过构造染色,研究系列平行图和Meredith图的无循环边着色.证明了最大度Δ(G)≥5的系列平行图G的无循环边色数a′(G)≤Δ(G)+1;同时证明了对于Meredith图G_k,有a′(G_k)=Δ(G_k).The acyclic edge colorings of series-parallel graphs and Meredith graphs are studied by using mathematical induction and constructing colorings. It is proved that if the maximum degree Δ（G）≥5,the acyclic edge chromatic index a′（G）≤Δ（G）＋ 1 for series-parallel graph G. And it is proved that a′（Gk）= Δ（Gk） for Meredith graph Gk.

关 键 词：系列平行图 Meredith图 无循环边着色 无循环边色数 

分 类 号：O157.5[理学—数学]