کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
419440 683808 2012 13 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Acyclic edge coloring of planar graphs with ΔΔ colors
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Acyclic edge coloring of planar graphs with ΔΔ colors
چکیده انگلیسی

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.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 160, Issue 9, June 2012, Pages 1356–1368
نویسندگان
, , , , ,