ICS Theory Group

Spring 2016: Theory Seminar
DBH, Room 1423, 1:00pm


May 13, 2016:

A note on acyclic edge coloring of complete bipartite graphs

By Manu Basavaraju and L. Sunil Chandran

Presented by Siddharth Gupta

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). In this paper, the authors prove that a'(Kp,p) = p+2 = Delta+2 when p is prime. They also show that if we remove any edge from Kp,p, the resulting graph is acyclically Delta + 1 = p + 1-edge-colorable.