کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
420145 683897 2012 11 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Acyclic edge colouring of plane graphs
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Acyclic edge colouring of plane graphs
چکیده انگلیسی

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. 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 χ′(G)χ′(G).In 1978, Fiamčík conjectured that for any graph GG it holds χ′(G)≤Δ(G)+2χ′(G)≤Δ(G)+2, where Δ(G)Δ(G) stands for the maximum degree of GG. This conjecture has been verified by now only for some special classes of graphs. In 2010, Borowiecki and Fiedorowicz confirmed it for planar graph with girth at least 5. In this paper, we improve the above result, by proving that if GG is a plane graph such that for each pair i,j∈{3,4}i,j∈{3,4}, no ii-face and a jj-face share a common vertex in GG, then χ′(G)≤Δ(G)+2χ′(G)≤Δ(G)+2.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 160, Issues 10–11, July 2012, Pages 1513–1523
نویسندگان
,