Acyclic edge coloring of sparse graphs

arXiv1202.6129MaRDI QIDQ6231297FDOQ6231297

Authors: Jianfeng Hou 

Publication date: 28 February 2012

Abstract: 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{\text{'}}_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{\text{'}}_a(G)leqDelta(G)+2$; if $mad(G)<3$, then $chi{\text{'}}_a(G)leqDelta(G)+1$. This implies that every triangle-free planar graph $G$ is acyclically edge $(Delta(G)+2)$-colorable.

This page was built for publication: Acyclic edge coloring of sparse graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6231297)