Acyclic Edge Coloring of Graphs with Maximum Degree 4
| dc.creator | Basavaraju, Manu | |
| dc.creator | Chandran, L. Sunil | |
| dc.date | 2008-01-11 | |
| dc.date.accessioned | 2026-07-07T08:53:48Z | |
| dc.date.available | 2026-07-07T08:53:48Z | |
| dc.description | 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 Δ+2$, where $Δ=Δ(G)$ denotes the maximum degree of $G$. We prove the conjecture for connected graphs with $Δ(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 $Δ(G) \le 4$. It follows that for any graph $G$ if $Δ(G) \le 4$, then $a'(G) \le 7$. | |
| dc.description | 13 pages | |
| dc.identifier | https://arxiv.org/abs/0801.1744 | |
| dc.identifier | http://arxiv.org/abs/0801.1744 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/145750 | |
| dc.subject | Combinatorics | |
| dc.title | Acyclic Edge Coloring of Graphs with Maximum Degree 4 | |
| dc.type | text |