摘要
利用差值转移的方法证明了,如果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.
出处
《淮阴师范学院学报(自然科学版)》
CAS
2011年第5期393-398,共6页
Journal of Huaiyin Teachers College;Natural Science Edition
基金
中央高校基本科研业务费专项基金资助项目(2010LKSX06)
关键词
无圈染色
平面图
围长
最大平均度
acyclic chromatic index
planeproblems
girth
maximum average degree