Acyclic edge coloring of sparse graphs

Details Acyclic edge coloring of sparse graphs Acyclic edge coloring of sparse graphs

2012-02-28

arxiv.org/abs/1202.6129v1

Mathematics

Combinatorics

Scientific paper

A proper edge coloring of a graph $G$ is called acyclic if there is no bichromatic cycle in $G$. The acyclic chromatic index of $G$, denoted by $\chi'_a(G)$, is the least number of colors $k$ such that $G$ has an acyclic edge $k$-coloring. The maximum average degree of a graph $G$, denoted by $\mad(G)$, is the maximum of the average degree of all subgraphs of $G$. In this paper, it is proved that if $\mad(G)<4$, then $\chi'_a(G)\leq{\Delta(G)+2}$; if $\mad(G)<3$, then $\chi'_a(G)\leq{\Delta(G)+1}$. This implies that every triangle-free planar graph $G$ is acyclically edge $(\Delta(G)+2)$-colorable.

Affiliated with

Also associated with

No associations

Rating

Acyclic edge coloring of sparse graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Acyclic edge coloring of sparse graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Acyclic edge coloring of sparse graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-605571