A note on acyclic edge coloring of complete bipartite graphs |
| |
Authors: | Manu Basavaraju |
| |
Affiliation: | Department of Computer Science and Automation, Indian Institute of Science, Bangalore-560012, India |
| |
Abstract: | An acyclic edge coloring of a graph is a proper edge coloring such that there are no bichromatic (2-colored) cycles. The acyclic chromatic index of a graph is the minimum number k such that there is an acyclic edge coloring using k colors and is denoted by a′(G). 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. Alon, McDiarmid and Reed observed that a′(Kp−1,p−1)=p for every prime p. In this paper we prove that a′(Kp,p)≤p+2=Δ+2 when p is prime. Basavaraju, Chandran and Kummini proved that a′(Kn,n)≥n+2=Δ+2 when n is odd, which combined with our result implies that a′(Kp,p)=p+2=Δ+2 when p is an odd prime. Moreover we show that if we remove any edge from Kp,p, the resulting graph is acyclically Δ+1=p+1-edge-colorable. |
| |
Keywords: | Acyclic edge coloring Acyclic edge chromatic index Matching Complete bipartite graphs |
本文献已被 ScienceDirect 等数据库收录! |
|