کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4649394 1342452 2010 11 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Acyclic edge colouring of planar graphs without short cycles
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
Acyclic edge colouring of planar graphs without short cycles
چکیده انگلیسی

Let G=(V,E)G=(V,E) be any finite graph. A mapping C:E→[k]C:E→[k] is called an acyclic edge  kk-colouring   of GG, if any two adjacent edges have different colours and there are no bichromatic cycles in GG. In other words, for every pair of distinct colours ii and jj, the subgraph induced in GG by all the edges which have colour ii or jj, is acyclic. The smallest number kk of colours, such that GG has an acyclic edge kk-colouring is called the acyclic chromatic index   of GG, denoted by χa′(G).In 2001, Alon et al. conjectured that for any graph GG it holds that χa′(G)≤Δ(G)+2; here Δ(G)Δ(G) stands for the maximum degree of GG.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,84,6,8 and 9. We also show that χa′(G)≤Δ(G)+1 if GG 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 GG is such a graph, then χa′(G)≤Δ(G)+15.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 310, Issue 9, 6 May 2010, Pages 1445–1455
نویسندگان
, ,