
arXiv: 0803.2433
AbstractAn 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′(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 series–parallel 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′(G)⩽Δ + 2, where Δ = Δ(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′(G)⩽Δ + 1. © 2010 Wiley Periodicals, Inc. J Graph Theory 69: 1–27, 2012
acyclic edge chromatic number, parallel graphs, 511, acyclic edge coloring, School of Automation), 2-degenerate graphs, Planar graphs; geometric and topological aspects of graph theory, Coloring of graphs and hypergraphs, 05C15, outer planar graphs, Computer Science & Automation (Formerly, FOS: Mathematics, Mathematics - Combinatorics, series, Combinatorics (math.CO)
acyclic edge chromatic number, parallel graphs, 511, acyclic edge coloring, School of Automation), 2-degenerate graphs, Planar graphs; geometric and topological aspects of graph theory, Coloring of graphs and hypergraphs, 05C15, outer planar graphs, Computer Science & Automation (Formerly, FOS: Mathematics, Mathematics - Combinatorics, series, Combinatorics (math.CO)
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 16 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Top 10% | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Top 10% | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Top 10% |
