Upper bounds for the star chromatic index of multipartite graphs

Sammanfattning

A star edge coloring is any edge coloring which is both proper and contains no cycles or path of length four which are bicolored, and the star chromatic index of a graph is the smallest number of colors for which that graph can be star edge colored. Star edge coloring is a relatively new field in graph theory, and very little is known regarding upper bounds of the star chromatic index of most graph types, one of these families being multipartite graphs. We investigate a method for obtaining upper bounds on the star chromatic index of complete multipartite graphs. The basic idea is to decompose such graphs into smaller complete bipartite graphs and applying known upper bounds for such graphs.This method has also been implemented and we present a hypothesis based on simulations.