# Star Bicolouring of Bipartite Graphs
## 3 ILP for Star Bicolouring  
We used the set cover formulation for the colouring problem, with additional constraints on paths. For \(s\subseteq L\), \(R\), let \(x_{s}\) be a binary variable. If \(x_{s}\) is \(1\), then all the vertices in \(s\) have the same colour. The following is an integer programming formulation for the star colouring problem. Denote as \(P\) the set of length-four paths in graph \(G\) and as \(\mathcal{P}(\cdot)\) the power set.  
\[\min\sum_{a\in\mathcal{P}(L)}x_{a}+\sum_{b\in\mathcal{P}(R)}x_{b}\] \[\sum_{a\in\mathcal{P}(L):v\in a}x_{a}=1 \forall\ v\in L\] \[\sum_{b\in\mathcal{P}(R):v\in b}x_{b}=1 \forall\ v\in R\] \[\sum_{s^{\top}p\
eq\phi}x_{s}\geq 3 \forall\ p\in P\] \[x_{s}\in\{0,1\} \forall\ s\in\mathcal{P}(L),\mathcal{P}(R).\]  
The first two constraints are the 'proper' colouring constraints. They state that each node must be assigned a unique colour, and the two sides of the bipartite graph do not share a colour. The first two equality constraints also ensure that the sets chosen as the solution to the integer program above are a partition of the vertex set. The last constraint ensures that each path has at least three colours. To see this, suppose for the sake of contradiction that some path \(p\) is not properly coloured, but the last constraint is satisfied for path \(p\). There are at least three sets \(a,b,c\) that have empty intersection with path \(p\). Sets \(a,b,c\) do not have a common intersection pairwise. Therefore, at least three nodes in \(p\) obtain distinct colours. If we drop the last set of integrality constraints in the ILP above, then the problem is referred to as the fractional star colouring problem. The optimum value to the fractional star colouring instance \(G\), denoted as \(\chi_{fs}\), is a lower bound on \(\chi_{s}(G)\). We compute \(\chi_{fs}\) using column generation. The ILP formulation above is exponential in the size of the graph.  
We examine the integrality gap of this formulation next. For a bipartite graph \(G\), the ratio \(g(G)=\frac{\chi_{s}(G)}{\chi_{fs}(G)}\) is known as the integrality gap for instance \(G\). The integrality gap for star bicolouring is the maximum integrality gap over all the inputs, which are \(\max_{G}g(G)\). We note that the integraliy gap of the formulation is unbounded. Let \(K_{n,n}\) be the complete bipartite graph on \(2n\) vertices, where the two partitions are of the same size \(n\).  
**Observation: 1**.: _The integrality gap for \(K_{n,n}\) is \(O(n)\)--more precisely, \(g(K_{n,n})\geq n/4\)._  
Note that if a total of \(n-1\) colours are used; then, each side in the bipartition has some two vertices of the same colour. This means that there is a path of over four vertices that is two-coloured. Hence, \(\chi(s)(G)\geq n\). Next, we give a feasible solution to the LP relaxation with an objective value of four. The size of the power sets \(\mathcal{P}(L)\) and \(\mathcal{P}(R)\) is \(2^{n}\) each. Each vertex \(v\in L(R)\) belongs to \(2^{n-1}\) subsets in \(\mathcal{P}(L)(\mathcal{P}(R))\). Consider a fractional solution in which for each \(s\in\mathcal{P}(L)\cup\mathcal{P}(R)\), \(x_{s}=2/2^{n}\). For each vertex \(v\in L\) we have,  
\[\sum_{s\in\mathcal{P}(L):v\in s}x_{s}=2^{n-1}*2/2^{n}=1.\]  
The same holds for \(v\in R\).  
So, the first two constraints are satisfied by this solution. For each path \(p\), there are two vertices in \(L\) and two in \(R\). The subsets of \(L(R)\) that intersect path \(p\) can be divided into three groups: ones that contain exactly one of the two vertices from the path and ones that contain exactly two vertices in that path. The number of each such subset is \(2^{n-2}\). Therefore, the total number of subsets of \(L\) intersecting \(p\) is \(3*2^{n-2}\). Similar reasoning holds for \(R\). Therefore, \(\sum_{s:s^{n}p\
eq q}x_{s}\geq 2/2^{n}*(6*2^{n-2})=3\). So, the solution \(x_{s}=2/2^{n}\) is feasible. The value of the objective function is \(2*2^{n}*2/2^{n}=4\).