Article ID Journal Published Year Pages File Type
6423568 Discrete Mathematics 2011 6 Pages PDF
Abstract

Let Δ denote the maximum degree of a graph. Fiamčík first and then Alon et al. again conjectured that every graph is acyclically edge (Δ+2)-colorable. Even for planar graphs, this conjecture remains open. It is known that every triangle-free planar graph is acyclically edge (Δ+5)-colorable. This paper proves that every planar graph without intersecting triangles is acyclically edge (Δ+4)-colorable.

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