# 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 $\chi'_{st}(G)$. 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 $k\geq1$, the star chromatic index is proven to satisfy$\chi'_{st}(B_k) \leq k^2 - k + 1$. For bipartite graphs $B_{k,n}$, 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 satisﬁes $\chi'_{st}(Bk,n) \leq k^2 -2k + n + 1, k \geq n > 1$. We also prove an upper bound for a special case of multipartite graphs, namely $K_{n,1,1,\dots,1}$ with m parts of size one. The star chromatic index of such a graph satisﬁes$\chi'_{st}(K_{n,1,1,\dots,1}) \leq 15\lceil\frac{n}{8}\rceil\cdot\lceil\frac{m}{8}\rceil + \frac{1}{2}m(m-1),\,m \geq 5$. For complete multipartite graphs where m < 5, we prove lower upper bounds than the one above.