1. A note on acyclic edge coloring of complete bipartite graphs
- Author
-
Basavaraju, Manu and Sunil Chandran, L.
- Subjects
- *
GRAPH coloring , *COMPLETE graphs , *BIPARTITE graphs , *PATHS & cycles in graph theory , *MATHEMATICAL analysis - Abstract
Abstract: An acyclic edge coloring of a graph is a proper edge coloring such that there are no bichromatic (2-) cycles. The acyclic chromatic index of a graph is the minimum number such that there is an acyclic edge coloring using colors and is denoted by . Let denote the maximum degree of a vertex in a graph . A complete bipartite graph with vertices on each side is denoted by . Alon, McDiarmid and Reed observed that for every prime . In this paper we prove that when is prime. Basavaraju, Chandran and Kummini proved that when is odd, which combined with our result implies that when is an odd prime. Moreover we show that if we remove any edge from , the resulting graph is acyclically -edge-colorable. [Copyright &y& Elsevier]
- Published
- 2009
- Full Text
- View/download PDF