On Acyclic Edge-Coloring of Complete Bipartite Graphs

Abstract

An acyclic edge-coloring of a graph is a proper edge-coloring without bichromatic ($2$-colored) cycles. The acyclic chromatic index of a graph $G$, denoted by $a^{\prime }(G)$, is the least integer $k$ such that $G$ admits an acyclic edge-coloring using $k$ colors. Let $\Delta =\Delta (G)$ denote the maximum degree of a vertex in a graph $G$. A complete bipartite graph with $n$ vertices on each side is denoted by $K_{n,n}$. Basavaraju, Chandran and Kummini proved that $a^{\prime }(K_{n,n})\ge n+2=\Delta +2$ when $n$ is odd. Basavaraju and Chandran provided an acyclic edge-coloring of $K_{p,p}$ using $p+2$ colors and thus establishing $a^{\prime }(K_{p,p})=p+2=\Delta +2$ when $p$ is an odd prime. The main tool in their approach is perfect $1$-factorization of $K_{p,p}$. Recently, following their approach, Venkateswarlu and Sarkar have shown that $K_{2p-1,2p-1}$ admits an acyclic edge-coloring using $2p+1$ colors which implies that $a^{\prime }(K_{2p-1,2p-1})=2p+1=\Delta +2$, where $p$ is an odd prime. In this paper, we generalize this approach and present a general framework to possibly get an acyclic edge-coloring of $K_{n,n}$ which possess a perfect $1$-factorization using $n+2=\Delta +2$ colors. In this general framework, we show that $K_{p^2,p^2}$ admits an acyclic edge-coloring using $p^2+2$ colors and thus establishing $a^{\prime }(K_{p^2,p^2})=p^2+2=\Delta +2$ when $p\ge 5$ is an odd prime.

17 pages, 10 figures