کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
427878 686571 2011 5 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Acyclic chromatic index of planar graphs with triangles
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Acyclic chromatic index of planar graphs with triangles
چکیده انگلیسی

A proper edge coloring of a graph G is called acyclic if there is no 2-colored cycle in G. The acyclic chromatic index of G  , denoted by χa′(G), is the least number of colors in an acyclic edge coloring of G. Let G   be a planar graph with maximum degree Δ(G)Δ(G). In this paper, we show that χa′(G)⩽Δ(G)+4, if G   contains no 4-cycle; χa′(G)⩽Δ(G)+5, if G   contains no intersecting triangles; and χa′(G)⩽Δ(G)+6 if G contains no adjacent triangles.


► We study acyclic edge coloring of planar graphs with maximum degree D  .
► Planar graphs without 4-cycles are acyclically (D+4)(D+4)-colorable.
► Planar graphs without intersecting triangles are acyclically (D+5)(D+5)-colorable.
► Planar graphs without adjacent triangles are acyclically (D+6)(D+6)-colorable.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information Processing Letters - Volume 111, Issue 17, 15 September 2011, Pages 836–840
نویسندگان
, , ,