Acyclic edge coloring of sparse graphs

作者：Wang Yingqian^*; Sheng Ping

来源：Discrete Mathematics, 2012, 312(24): 3561-3573.

DOI：10.1016/j.disc.2012.08.012

• Acyclic edge coloring
• Maximum average degree
• Triangle-free planar graphs

Let Delta denote the maximum degree of a graph. Fiamcik first, Alon, Sudakov and Zaks later conjectured that every graph is acyclically edge (Delta + 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 (Delta + 2)-colorable.

• 出版日期2012-12-28
• 单位浙江师范大学