کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
427960 686581 2010 6 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Some results on acyclic edge coloring of plane graphs
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Some results on acyclic edge coloring of plane graphs
چکیده انگلیسی

An acyclic edge coloring of a graph is a proper edge coloring without bichromatic cycles. The acyclic chromatic index of a graph G, denoted by α′(G), is the minimum number k such that G admits an acyclic edge coloring using k colors. Let G be a plane graph with maximum degree Δ and girth g. In this paper, we prove that α′(G)=Δ(G) if one of the following conditions holds: (1) Δ⩾8 and g⩾7; (2) Δ⩾6 and g⩾8; (3) Δ⩾5 and g⩾9; (4) Δ⩾4 and g⩾10; (5) Δ⩾3 and g⩾14. We also improve slightly a result of A. Fiedorowicz et al. (2008) [7] by showing that every triangle-free plane graph admits an acyclic edge coloring using at most Δ(G)+5 colors.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information Processing Letters - Volume 110, Issue 20, 30 September 2010, Pages 887-892