Acyclic Edge Coloring of Graphs with Maximum Degree 4

Details Acyclic Edge Coloring of Graphs with Maximum Degree 4 Acyclic Edge Coloring of Graphs with Maximum Degree 4

2008-01-11

arxiv.org/abs/0801.1744v1

Mathematics

Combinatorics

13 pages

Scientific paper

An $acyclic$ edge coloring of a graph is a proper edge coloring such that there are no bichromatic cycle s. The \emph{acyclic chromatic index} of a graph is the minimum number k such that there is an acyclic e dge coloring using k colors and is denoted by $a'(G)$. It was conjectured by Alon, Sudakov and Zaks that for any simple and finite graph $G$, $a'(G)\le \Delta+2$, where $\Delta =\Delta(G)$ denotes the maximum degree of $G$. We prove the conjecture for connected graphs with $\Delta(G) \le 4$, with the additional restriction that $m \le 2n-1$, where $n$ is the number of vertices and $m$ is the number of edges in $G $. Note that for any graph $G$, $m \le 2n$, when $\Delta(G) \le 4$. It follows that for any graph $G$ if $\Delta(G) \le 4$, then $a'(G) \le 7$.

Affiliated with

Also associated with

No associations

Rating

Acyclic Edge Coloring of Graphs with Maximum Degree 4 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 Graphs with Maximum Degree 4, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Acyclic Edge Coloring of Graphs with Maximum Degree 4 will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-547697