平面图的无圈边染色  

Acyclic Edge Colouring of Pianar Graphs

作　　者：段娟娟[1] 丁伟[1] 

机构地区：[1]中国矿业大学理学院,江苏徐州221116

出　　处：《淮阴师范学院学报（自然科学版）》2011年第5期393-398,共6页Journal of Huaiyin Teachers College;Natural Science Edition

基　　金：中央高校基本科研业务费专项基金资助项目(2010LKSX06)

摘　　要：利用差值转移的方法证明了,如果g(G)≥4则有X′a≤Δ(G)+4.图G=(V,E)是简单图,映射C:E→[k],被称作是图G的一个无圈k边染色.如果任意相邻的两个边染有不同的颜色,以及图G中不含有2-色圈,换句话说即图G中任何染两种颜色的边的导出子图是一棵森林.Let G=（V,E） be any finite graph.A mapping C：E→[k]is called an acyclic edge colouring of G,if any two adjacent edges have different colours and there are no bichromatic cycles in G.In other words,the subgraph induced by the union of any two colour classes is a forest.The minimum number k of colours,such that G has an acyclic edge k-colouring is called the acyclic chromatic index of G,denoted by X′a（G）.Alon et al.conjectured that for any graph G it holds that X′a（G）≤Δ（G）＋2;here Δ（G） stands for the maximum degree of G.In this paper weprove the planar graphs with girth at least 4,then X′a≤Δ（G）＋4.

关 键 词：无圈染色 平面图 围长 最大平均度 

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