Mathematics – Combinatorics
Scientific paper
2008-04-29
Mathematics
Combinatorics
4 pages
Scientific paper
An $acyclic$ edge coloring of a graph is a proper edge coloring such that there are no bichromatic cycles. The \emph{acyclic chromatic index} of a graph is the minimum number k such that there is an acyclic edge coloring using k colors and is denoted by $a'(G)$. It was conjectured by Alon, Sudakov and Zaks (and earlier by Fiamcik) that $a'(G)\le \Delta+2$, where $\Delta =\Delta(G)$ denotes the maximum degree of the graph. Alon et.al also raised the question whether the complete graphs of even order are the only regular graphs which require $\Delta+2$ colors to be acyclically edge colored. In this paper, using a simple counting argument we observe not only that this is not true, but infact all d-regular graphs with $2n$ vertices and $d > n$, requires at least $d+2$ colors. We also show that $a'(K_{n,n}) \ge n+2$, when $n$ is odd using a more non-trivial argument(Here $K_{n,n}$ denotes the complete bipartite graph with $n$ vertices on each side). This lower bound for $K_{n,n}$ can be shown to be tight for some families of complete bipartite graphs and for small values of $n$. We also infer that for every $d,n$ such that $d \ge 5$, $n \ge 2d + 3$ and $dn$ even, there exist $d$-regular graphs which require at least $d+2$-colors to be acyclically edge colored.
Basavaraju Manu
Chandran Sunil L.
Kummini Manoj
No associations
LandOfFree
$d$-Regular graphs of acyclic chromatic index at least $d+2$ 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 $d$-Regular graphs of acyclic chromatic index at least $d+2$, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and $d$-Regular graphs of acyclic chromatic index at least $d+2$ will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-210342