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 .In 2001, Alon et al. conjectured that for any graph G it holds that ; 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 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 . |
| |
Keywords: | Acyclic edge colouring Planar graph |
本文献已被 ScienceDirect 等数据库收录! |
|