An algorithm for coloring some perfect graphs (Q1382811): Difference between revisions
From MaRDI portal
Removed claims |
Changed an Item |
||
Property / author | |||
Property / author: Hacène Ait Haddadene / rank | |||
Normal rank | |||
Property / reviewed by | |||
Property / reviewed by: Timothy R. S. Walsh / rank | |||
Normal rank |
Revision as of 03:23, 14 February 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | An algorithm for coloring some perfect graphs |
scientific article |
Statements
An algorithm for coloring some perfect graphs (English)
0 references
14 September 1998
0 references
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.
0 references
chromatic number
0 references
colouring
0 references
colouring algorithm
0 references
perfect graphs
0 references