首页 | 本学科首页   官方微博 | 高级检索  
     


Acyclic edge colouring of planar graphs without short cycles
Authors:Mieczys?aw Borowiecki
Affiliation:Faculty of Mathematics, Computer Science and Econometrics, University of Zielona Góra, Z.Szafrana 4a, 65-516 Zielona Góra, Poland
Abstract:
Let G=(V,E) be any finite graph. A mapping C:E→[k] is called an acyclic edgek-colouring of G, if any two adjacent edges have different colours and there are no bichromatic cycles in G. In other words, for every pair of distinct colours i and j, the subgraph induced in G by all the edges which have colour i or j, is acyclic. The smallest number k of colours, such that G has an acyclic edge k-colouring is called the acyclic chromatic index of G, denoted by View the MathML source.In 2001, Alon et al. conjectured that for any graph G it holds that View the MathML source; here Δ(G) stands for the maximum degree of G.In this paper we prove this conjecture for planar graphs with girth at least 5 and for planar graphs not containing cycles of length 4,6,8 and 9. We also show that View the MathML source if G is planar with girth at least 6. Moreover, we find an upper bound for the acyclic chromatic index of planar graphs without cycles of length 4. Namely, we prove that if G is such a graph, then View the MathML source.
Keywords:Acyclic edge colouring   Planar graph
本文献已被 ScienceDirect 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号