Acyclic chromatic indices of planar graphs with girth at least five

0.00 Avg rating—0 Votes

Article ID:	iaor2012242
Volume:	23
Issue:	1
Start Page Number:	140
End Page Number:	157
Publication Date:	Jan 2012
Journal:	Journal of Combinatorial Optimization
Authors:	Wang Weifan, Shu Qiaojun
Keywords:	optimization

Abstract:

An acyclic edge coloring of a graph G is a proper edge coloring such that no bichromatic cycles are produced. The acyclic chromatic index a′(G) of G is the smallest integer k such that G has an acyclic edge coloring using k colors. In this paper, we prove that every planar graph G with girth g(G)≥5 and maximum degree δ≥12 has a′(G)=δ.

Reviews

Required fields are marked *. Your email address will not be published.