# Star Bicolouring of Bipartite Graphs
## 1 Introduction
[11] showed an upper bound of \(\leq k^{2}-k+2\), where \(k\) is the maximum degree sufficient for star colouring. For a maximum degree of at most three, they show that seven colours suffice for star colouring. For graphs with maximum average degrees of at most \(26/11,18/7,8/3\), [PERSON] et al. [15] showed that the star chromatic number is at most four, five, and six, respectively. [PERSON] et al. [13] showed that \(k^{3/2}\) colours suffice for star colouring, and they exhibited a graph for which \(\Omega(k^{3}/\log n)\) are needed. Let us denote the minimum number of colours for star bicolouring of a bipartite graph \(G=(L,R,E)\) with \(\chi_{s}(G)\). The following general lower [5; 16] and upper bounds are known. \[\frac{|E|}{\max\{|L|,|R|\}}\leq\chi_{s}(G)\leq\min\{|L|,|R|\}+1 \tag{1}\]  
The upper bound is evident, as one can always colour one side with a single colour, and the other side uses a different colour for each node. This bound is quite weak. [PERSON] and [PERSON] [5] gave an approximation algorithm for the star bicolouring problem. The algorithm works by calculating distance-2 independent sets, greedily, of vertices (from either \(L\) or \(R\)) containing a vertex with the highest degree and then assigning them all to the same colour class. The choice of independent sets from \(L\) or \(R\) is based on the average maximum degree in \(L,R\). This algorithm has an approximation ratio of \(O(n^{2/3})\) and a time complexity of \(O(m^{2}\sqrt{n})\), where \(n\) is the number of vertices, and \(m\) is the number of edges in the \(G\). The bipartite graphs that typically arise in the context of the applications, described in the next section, are large but sparse. Several efficient heuristic methods that perform well in practice have been proposed over the years for the star bicolouring problem [3; 5; 6; 8]. Studies have reported successive reductions in the number of colours required for the standardised set of test matrices such as the Harwell-Boeing collection [17]. A lower bound on star colouring number is also a lower bound on the star bicolouring number (for bipartite graphs). The upper bounds computed using heuristic methods are still far from the lower bound in Equation (1). Therefore, it is natural to develop stronger lower bounds for star bicolouring, and this motivates our study. Contributions: The main contributions of this paper include a novel method to solve the star bicolouring problem and the derivation of new results for various bipartite graphs that arise in the field of numerical optimisation. We provide an exponentially sized integer linear program (ILP) whose optimal solution has value \(\chi_{s}(G)\) and which usesthe linear programming (LP) relaxation to compute a lower bound on \(\chi_{s}(G)\). The ILP is exponentially sized; therefore, we give a column generation method to solve the LP. The pricing problem to be solved is modelled as an ILP. We also give computationally efficient heuristic to solve the pricing problem. We use the method of iterative rounding [18] to compute an upper bound on the star bichromatic number. The computational results indicate that our lower bound obtained using the column generation procedure is close to the upper bound computed using the iterative method in practice for sparse bipartite graphs. Our method is general and can easily be adapted to handle colouring constraints on other structures. For instance, acyclic colourings of bipartite graphs can be found using the approach presented here. To the best of our knowledge, this is the first such formulation and computational study for the star bicolouring problem. Results:We ran small-sized computational experiments that evaluate linear programming relaxation and an iterative rounding approach to determine the star bicolouring number of bipartite graphs. The details are in Section 6.1. The algorithms were programmed in the GNU Octave and GLPK to solve the linear programming (LP) relaxation using column generation.