The star chromatic index $\chi'_{S}(G)$ of a graph $G$ is the minimum number of colors needed to properly color the edges of the graph so that no path or cycle of length four is bi-colored. We obtain a near-linear upper bound in terms of the maximum degree $\Delta = \Delta (G)$. Our best lower bound on $\chi'_{S}$ in terms of $\Delta $ is $2\Delta (1+o(1))$ valid for complete graphs. We also consider the special case of cubic graphs, for which we show that the star chromatic index lies between 4 and 7 and characterize the graphs attaining the lower bound. The proofs involve a variety of notions from other branches of mathematics and may therefore be of certain independent interest.

COBISS.SI-ID: 16925273

In the first part of this paper we unify the motivations and approaches to two very famous lower bounds for the chromatic number of a graph and rewrite them in a very similar settings which are easy to understand and straightforward to implement. In the second part of the paper we provide explanations how to solve efficiently the resulting semidefinite programs and how to use optimal solutions to get good colouring heuristics.

COBISS.SI-ID: 2048193043

This article provides analysis of several copositive formulations of the Graph partitioning problem (GPP) and semidefinite relaxations based on them. We prove that the copositive formulations from Burer and Povh are equivalent and that they both imply semidefinite relaxations which are stronger than the Donath-Hoffman eigenvalue lower bound and projected semidefinite lower bound from Wolkowicz and Zhao.

COBISS.SI-ID: 1024318017