Back to Search
Start Over
A note on acyclic edge coloring of complete bipartite graphs
- Source :
-
Discrete Mathematics . Jul2009, Vol. 309 Issue 13, p4646-4648. 3p. - Publication Year :
- 2009
-
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]
Details
- Language :
- English
- ISSN :
- 0012365X
- Volume :
- 309
- Issue :
- 13
- Database :
- Academic Search Index
- Journal :
- Discrete Mathematics
- Publication Type :
- Academic Journal
- Accession number :
- 39353413
- Full Text :
- https://doi.org/10.1016/j.disc.2009.01.014