平面图的无圈边染色

利用差值转移的方法证明了,如果g（G）≥4则有X′a≤Δ（G）＋4.图G=（V,E）是简单图,映射C：E→k],被称作是图G的一个无圈k边染色.如果任意相邻的两个边染有不同的颜色,以及图G中不含有2-色圈,换句话说即图G中任何染两种颜色的边的导出子图是一棵森林.

Acyclic Edge Colouring of Pianar Graphs

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.