Upper bounds on the star chromatic index for bipartite graphs

Abstract: An area in graph theory is graph colouring, which essentially is a labeling of the vertices or edges according to certain constraints. In this thesis we consider star edge colouring, which is a variant of proper edge colouring where we additionally require the graph to have no two-coloured paths or cycles with length 4. The smallest number of colours needed to colour a graph G with a star edge colouring is called the star chromatic index of G and is denoted . This paper proves an upper bound of the star chromatic index of bipartite graphs in terms of the maximum degree; the maximum degree of G is the largest number of edges incident to a single vertex in G. For bipartite graphs Bk with maximum degree , the star chromatic index is proven to satisfy. For bipartite graphs , where all vertices in one part have degree n, and all vertices in the other part have degree k, it is proven that the star chromatic index satisfies . We also prove an upper bound for a special case of multipartite graphs, namely  with m parts of size one. The star chromatic index of such a graph satisfies. For complete multipartite graphs where m < 5, we prove lower upper bounds than the one above.