Article ID Journal Published Year Pages File Type
6423441 Discrete Mathematics 2012 13 Pages PDF
Abstract

Let Δ denote the maximum degree of a graph. Fiamčík first, Alon, Sudakov and Zaks later conjectured that every graph is acyclically edge (Δ+2)-colorable. In this paper, we prove this conjecture for graphs with maximum average degree less than 4. As a corollary, triangle-free planar graphs are acyclically edge (Δ+2)-colorable.

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, ,