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

The Acyclic Coloring of Meredith Graphs and Series-Parallel Graphs

作　　者：李自来[1] 张卫标[2] 

机构地区：[1]西京学院基础部,陕西西安710123 [2]商丘学院计算机科学与技术学院,河南商丘476000

出　　处：《四川师范大学学报（自然科学版）》2011年第3期318-320,共3页Journal of Sichuan Normal University（Natural Science）

基　　金：国家自然科学基金(10971164);陕西省自然科学基金(SJ08A24)资助项目

摘　　要：图G的无循环着色是指图G的顶点着色使得G的任何相邻的顶点不着双色且在图G没有双色圈.研究了Meredith图和系列平行图的无循环着色,证明了Δ(G)≥5的系列平行图的无循环色数a(G)≤Δ(G)+1.An acyclic coloring of a graph is a proper coloring such that there are no bichromatic cycles.In this paper,the acyclic coloring chromatic index of Meredith graphs and series-parallel graphs is studied.It is proved that a（G）≤Δ（G）＋1 for series-parallel graphs with Δ（G）≥5.

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

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