|کد مقاله||کد نشریه||سال انتشار||مقاله انگلیسی||ترجمه فارسی||نسخه تمام متن|
|4646798||1342314||2016||6 صفحه PDF||سفارش دهید||دانلود رایگان|
An acyclic edge-coloring of a graph is a proper edge-coloring without bichromatic (2-colored) cycles. The acyclic chromatic index of a graph GG, denoted by a′(G)a′(G), is the least integer kk such that GG admits an acyclic edge-coloring using kk colors. Let Δ=Δ(G)Δ=Δ(G) denote the maximum degree of a vertex in a graph GG. A complete bipartite graph with nn vertices on each side is denoted by Kn,nKn,n. Basavaraju, Chandran and Kummini proved that a′(Kn,n)≥n+2=Δ+2a′(Kn,n)≥n+2=Δ+2 when nn is odd. Basavaraju and Chandran showed that a′(Kp,p)≤p+2a′(Kp,p)≤p+2 which implies a′(Kp,p)=p+2=Δ+2a′(Kp,p)=p+2=Δ+2 when pp is an odd prime, and the main tool in their proof is perfect 1-factorization of Kp,pKp,p. In this paper we study the case of K2p−1,2p−1K2p−1,2p−1 which also possess perfect 1-factorization, where pp is odd prime. We show that K2p−1,2p−1K2p−1,2p−1 admits an acyclic edge-coloring using 2p+12p+1 colors and so we get a′(K2p−1,2p−1)=2p+1=Δ+2a′(K2p−1,2p−1)=2p+1=Δ+2 when pp is an odd prime.
Journal: Discrete Mathematics - Volume 339, Issue 1, 6 January 2016, Pages 72–77