Acyclic edge coloring of complete r-partite graphs

Abstract

An acyclic edge coloring of a graph G is a proper edge coloring of G which has no dichromatic cycle. The minimum number of colors required to acyclically edge color graph G is called its acyclic chromatic index, denoted a’ (G). In this thesis, we present an acyclic edge coloring for complete graphs Ka, b, where a>b and a is prime, using Δ (G) =a colors. An acyclic edge coloring for complete tripartite graphs, and r-partite graphs (r>3) is presented. These colorings follow patterns similar to those used in the case of complet bipartite graphs.