## 5 Algorithms for Random Perfect Graphs  
[PERSON], [PERSON], and [PERSON] [4] show that the stable set problem, the clique problem, the colouring problem, the clique covering problem and their weighted versions are computable in polynomial time for perfect graphs. The algorithms rely on the Lovasz sandwich theorem, which states that for every graph \(G\) we have \(\omega(G)\leq\vartheta(\overline{G})\leq\chi(G)\), where \(\vartheta(G)\) is the Lovasz number. The Lovasz number can be approximated via the ellipsoid method in polynomial time, and for perfect graphs we know that \(\omega(G)=\chi(G)\), hence \(\vartheta(G)\) is an integer and its precise value can be found. Therefore \(\chi(G)\) and \(\omega(G)\) can be found in polynomial time for perfect graphs, though these are NP-hard problems for general graphs. Further, \(\alpha(G)\) and \(\overline{\chi}(G)\) (the clique covering number) can be computed from the complement of \(G\) (which is perfect). The weighted versions of these parameters can be found in a similar way using the weighted version of the Lovasz number, \(\vartheta_{w}(G)\). These results tell us more about computational complexity than algorithm design in practice. On the other hand, the problems above are much more easily solvable for generalised split graphs. We know that the vast majority of the \(n\)-vertex perfect graphs are generalised split graphs [1]. One can first test if the input perfect graph is a generalised split graph using the algorithm in this paper and if so, apply a more efficient solution. [PERSON] and [PERSON] [5] show that, given a generalised split graph \(G\) with \(n\) vertices together with a unipolar representation of \(G\) or \(\overline{G}\), we can efficiently solve each of the following four problems: find a maximum clique, find a maximum independent set, find a minimum colouring, and find a minimum clique cover. It is sufficient to show that this is the case when \(G\) is unipolar, as otherwise we can solve the complementary problem in the complement of \(G\). Finding a maximum size stable set and minimum clique cover in a unipolar graph is equivalent to determining whether there exists a vertex in the central clique such that no side clique is contained in its neighbourhood, which is trivial and can be done very efficiently. Suppose there are \(k\) side cliques. If there is such a vertex \(v\), then a maximum size stable set (of size \(k+1\)) consists of \(v\) and from each side clique a vertex not adjacent to \(v\), and a minimum size clique cover is formed by the central clique and the \(k\) side cliques. If not, then a maximum size stable set (of size \(k\)) consists of a vertex from each side clique, and a minimum clique cover is formed by extending the \(k\) side cliques to maximal cliques (which then cover \(C_{0}\)). Let us focus on finding a maximum clique and minimum colouring of a unipolar graph \(G\) with a representation \(R\). If \(R\) contains \(k\) side cliques, \(C_{1},\ldots C_{k}\), then  
\[\omega(G)=\chi(G)=\max\{\omega(G[C_{0}\cup C_{i}])\}_{i=1}^{k}=\max\{\chi(G[C _{0}\cup C_{i}])\}_{i=1}^{k}\]  
where \(C_{0}\) is the central clique. Therefore, in order to find a maximum clique or a minimum colouring, it is sufficient to solve the corresponding problem in each of the co-bipartite graphs induced by the central clique and a side clique. The vertices outside a clique in a co-bipartite graph form a cover in the complementary bipartite graph, and the vertices coloured with the same colour in a proper colouring of a co-bipartite graph form a matching in the complementary bipartite graph. By [PERSON]'s theorem it is easy to find a minimum cover using a given maximum matching, and therefore finding a maximum clique and a minimum colouring in a co-bipartite graph is equivalent to finding a maximum matching in the complementary bipartite graph. For colourings, we explicitly find a minimum colouring in each co-bipartite graph \(G[C_{0}\cup C_{i}]\), and such colourings can be fitted together using no more colours, since \(C_{0}\) is a clique cutset.