Acyclic edge coloring of 2-degenerate graphs

作者：Basavaraju Manu^*; Chandran L Sunil

来源：Journal of Graph Theory, 2012, 69(1): 1-27.

DOI：10.1002/jgt.20559

• acyclic edge coloring
• acyclic edge chromatic number
• 2-degenerate graphs
• series-parallel graphs
• outer planar graphs

An acyclic edge coloring of a graph is a proper edge coloring such that there are no bichromatic cycles. The acyclic chromatic index of a graph is the minimum number k such that there is an acyclic edge coloring using k colors and is denoted by a%26apos;(G). A graph is called 2-degenerate if any of its induced subgraph has a vertex of degree at most 2. The class of 2-degenerate graphs properly contains seriesparallel graphs, outerplanar graphs, non - regular subcubic graphs, planar graphs of girth at least 6 and circle graphs of girth at least 5 as subclasses. It was conjectured by Alon, Sudakov and Zaks (and much earlier by Fiamcik) that a%26apos;(G)%26lt;=Delta + 2, where Delta = Delta(G) denotes the maximum degree of the graph. We prove the conjecture for 2-degenerate graphs. In fact we prove a stronger bound: we prove that if G is a 2-degenerate graph with maximum degree ?, then a%26apos;(G)%26lt;=Delta + 1.

• 出版日期2012-1