کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
427878 | 686571 | 2011 | 5 صفحه PDF | دانلود رایگان |
![عکس صفحه اول مقاله: Acyclic chromatic index of planar graphs with triangles Acyclic chromatic index of planar graphs with triangles](/preview/png/427878.png)
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.
Journal: Information Processing Letters - Volume 111, Issue 17, 15 September 2011, Pages 836–840