On acyclic edge-coloring of complete bipartite graphs

摘要

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'(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,K-n. Basavaraju, Chandran and Kummini proved that a'(K-n,K-n) >= n + 2 = Delta + 2 when n is odd. Basavaraju and Chandran provided an acyclic edge-coloring of K-p,K-p using p + 2 colors and thus establishing a'(K-p,K-p) = p + 2 = Delta + 2 when p is an odd prime. The main tool in their approach is perfect 1-factorization of Ica,. Recently, following their approach, Venkateswarlu and Sarkar have shown that K2p-1,(2p-1) admits an acyclic edge-coloring using 2p + 1 colors which implies that a'(K2p-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,K-n, which possesses a perfect 1-factorization using n + 2 = Delta + 2 colors. In this general framework, using number theoretic techniques, we show that K-p2,K-p2 admits an acyclic edge coloring with p(2) + 2 colors and thus establishing a'(K-p2,K-p2) = p(2) + 2 = Delta + 2 when p is an odd prime. (C) 2016 Elsevier B.V. All rights reserved.