An algorithm for coloring some perfect graphs (Q1382811): Difference between revisions

A graph \(G\) is perfect if every induced subgraph \(H\) of \(G\) has chromatic number \(\chi(H)\) equal to the size of a largest clique of \(H\). An algorithm for colouring a \(K_4\)-free perfect \(n\)-vertex graph \(G\) with \(\chi(G)\) colours in \(O(n^3)\) time was presented in [\textit{A. Tucker}, A reduction procedure for colouring perfect \(K_4\)-free graphs, J. Comb. Theory, Ser. B 43, No. 2, 151-172 (1987; Zbl 0634.05028)]. The present paper uses this algorithm to obtain an \(O(n^4)\)-time colouring algorithm for a larger class \({\mathcal G}\) of perfect graphs: \(G\) is in \({\mathcal G}\) if every induced subgraph has a vertex \(v\) whose neighbourhood \(\Gamma(v)\) has property P4: the union of any four triangles of \(\Gamma(v)\) contains a \(K_4\). The paper presents an \(O(n^6)\)-time algorithm to test property P4; the time taken to test a graph \(G\) for membership in \({\mathcal G}\) and to order its vertices \(v_1, \dots, v_n\) so that \(\Gamma(v_i)\) has property P4 in \(G- \{v_1, \dots, v_{i-1}\}\) for each \(i\) (a necessary pre-processing step for the colouring algorithm) is not given. The paper mentions an algorithm for colouring any perfect graph [\textit{M. Grötschel}, \textit{L. Lovász}, and \textit{A. Schrijver}, Polynomial algorithms for perfect graphs, Ann. Discrete Math. 21, 325-356 (1984; Zbl 0554.05041)] and states: ``their algorithm uses the ellipsoidal method and is not very efficient in practice.'' This reviewer would have liked to see a comparison of both the theoretical and experimental running times of the algorithm in [Grötschel et al., op. cit.] with the one in the paper under review including vertex ordering.