Header menu link for other important links
X
On acyclic edge-coloring of the complete bipartite graphs K2p-1,2p-1 for odd prime p
Published in Elsevier B.V.
2016
Volume: 339
   
Issue: 1
Pages: 72 - 77
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′(G), is the least integer k such that G admits an acyclic edge-coloring using k colors. Let Δ=Δ(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 Kn,n. Basavaraju, Chandran and Kummini proved that a′(Kn,n)≥ n+2=Δ+2 when n is odd. Basavaraju and Chandran showed that a′(Kp,p) ≤p+2 which implies a′(Kp,p)=p+2=Δ+2 when p is an odd prime, and the main tool in their proof is perfect 1-factorization of Kp,p. In this paper we study the case of K2p-1,2p-1 which also possess perfect 1-factorization, where p is odd prime. We show that K2p-1,2p-1 admits an acyclic edge-coloring using 2p+1 colors and so we get a′(K2p-1,2p-1)=2p+1=Δ+2 when p is an odd prime. © 2015 Elsevier B.V. All rights reserved.
About the journal
JournalData powered by TypesetDiscrete Mathematics
PublisherData powered by TypesetElsevier B.V.
ISSN0012365X
Open AccessYes