کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
419440 | 683808 | 2012 | 13 صفحه PDF | دانلود رایگان |
![عکس صفحه اول مقاله: Acyclic edge coloring of planar graphs with ΔΔ colors Acyclic edge coloring of planar graphs with ΔΔ colors](/preview/png/419440.png)
An acyclic edge coloring of a graph is a proper edge coloring without bichromatic cycles. In 1978, it was conjectured that Δ(G)+2Δ(G)+2 colors suffice for an acyclic edge coloring of every graph GG (Fiamčík, 1978 [8]). The conjecture has been verified for several classes of graphs, however, the best known upper bound for as special class as planar graphs are, is Δ+12Δ+12 (Basavaraju and Chandran, 2009 [3]). In this paper, we study simple planar graphs which need only Δ(G)Δ(G) colors for an acyclic edge coloring. We show that a planar graph with girth gg and maximum degree ΔΔ admits such acyclic edge coloring if g≥12g≥12, or g≥8g≥8 and Δ≥4Δ≥4, or g≥7g≥7 and Δ≥5Δ≥5, or g≥6g≥6 and Δ≥6Δ≥6, or g≥5g≥5 and Δ≥10Δ≥10. Our results improve some previously known bounds.
Journal: Discrete Applied Mathematics - Volume 160, Issue 9, June 2012, Pages 1356–1368