On acyclic edge-coloring of the complete bipartite graphs for odd prime

详细信息    查看全文

• 作者：Ayineedi Venkateswarlu^a ; ^{venku@isichennai.res.in" class="auth_mail" title="E-mail the corresponding author} ; Santanu Sarkar^b ; ^{santanu@iitm.ac.in" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Acyclic edge-coloring ; Acyclic chromatic index ; Perfect matching ; Perfect 1-factorization ; Complete bipartite graphs
• 刊名：Discrete Mathematics
• 出版年：2016
• 出版时间：6 January 2016
• 年：2016
• 卷：339
• 期：1
• 页码：72-77
• 全文大小：365 K

文摘

An acyclic edge-coloring of a graph is a proper edge-coloring without bichromatic (2-colored) cycles. The acyclic chromatic index of a graph md5=ea61a879876894947e0c9a718012ced4" title="Click to view the MathML source">G$G$, denoted by md5=5c536776334331888b8c1e74e1879c50" title="Click to view the MathML source">a^′(G)$a^{\prime }\left(G\right)$, is the least integer md5=0b4bf2a9be1c1c1565d15171bed675ca" title="Click to view the MathML source">k$k$ such that md5=ea61a879876894947e0c9a718012ced4" title="Click to view the MathML source">G$G$ admits an acyclic edge-coloring using md5=0b4bf2a9be1c1c1565d15171bed675ca" title="Click to view the MathML source">k$k$ colors. Let md5=52266eda64bc4a6cc30ae9d33338159e" title="Click to view the MathML source">Δ=Δ(G)$\Delta =\Delta \left(G\right)$ denote the maximum degree of a vertex in a graph md5=ea61a879876894947e0c9a718012ced4" title="Click to view the MathML source">G$G$. A complete bipartite graph with md5=b8e50083be13ac31eb77990ba59d7108" title="Click to view the MathML source">n$n$ vertices on each side is denoted by md5=181887ef92ae2e5c5fc309175b97c829" title="Click to view the MathML source">K_n,n$K_{n,n}$. Basavaraju, Chandran and Kummini proved that md5=85d6e6cea70d0092d89e9bd9bea7370e" title="Click to view the MathML source">a^′(K_n,n)≥n+2=Δ+2$a^{\prime }\left(K_{n,n}\right)\ge n+2=\Delta +2$ when md5=b8e50083be13ac31eb77990ba59d7108" title="Click to view the MathML source">n$n$ is odd. Basavaraju and Chandran showed that md5=60c0803a0d3591bc1d00f2d83a696bec" title="Click to view the MathML source">a^′(K_p,p)≤p+2$a^{\prime }\left(K_{p,p}\right)\le p+2$ which implies md5=9e10f8e660245413bc756d605c820b7d" title="Click to view the MathML source">a^′(K_p,p)=p+2=Δ+2$a^{\prime }\left(K_{p,p}\right)=p+2=\Delta +2$ when md5=56b64d14828c696f2734530f653a678b" title="Click to view the MathML source">p$p$ is an odd prime, and the main tool in their proof is perfect 1-factorization of md5=488dac5377ae6ee09e85276fa4b85407" title="Click to view the MathML source">K_p,p$K_{p,p}$. In this paper we study the case of md5=f163411de9a8610d8295bae9f8020636" title="Click to view the MathML source">K_{2p−1,2p−1}$K_{2p-1,2p-1}$ which also possess perfect 1-factorization, where md5=56b64d14828c696f2734530f653a678b" title="Click to view the MathML source">p$p$ is odd prime. We show that md5=f163411de9a8610d8295bae9f8020636" title="Click to view the MathML source">K_{2p−1,2p−1}$K_{2p-1,2p-1}$ admits an acyclic edge-coloring using md5=fa997ddf38a7563a7f590219e7acfd6a" title="Click to view the MathML source">2p+1$2p+1$ colors and so we get md5=891456e659e2abc37aae233d768bf0a7" title="Click to view the MathML source">a^′(K_{2p−1,2p−1})=2p+1=Δ+2$a^{\prime }\left(K_{2p-1,2p-1}\right)=2p+1=\Delta +2$ when md5=56b64d14828c696f2734530f653a678b" title="Click to view the MathML source">p$p$ is an odd prime.