An algorithm for coloring some perfect graphs
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.
- Precoloring Extension III: Classes of Perfect Graphs
- Coloring perfect \((K_ 4\)-e)-free graphs
- A reduction procedure for coloring perfect \(K_ 4\)-free graphs
- On-line coloring of perfect graphs
- Perfect graphs
- scientific article; zbMATH DE number 108587
- scientific article; zbMATH DE number 4202279
- scientific article; zbMATH DE number 3869356
- Perfectly colorable graphs
- Efficient parallel and sequential algorithms for 4-coloring perfect planar graphs
- A reduction procedure for coloring perfect \(K_ 4\)-free graphs
- Coloring perfect \((K_ 4\)-e)-free graphs
- scientific article; zbMATH DE number 3882470 (Why is no real title available?)
- scientific article; zbMATH DE number 3168327 (Why is no real title available?)
- scientific article; zbMATH DE number 3859178 (Why is no real title available?)
- On rigid circuit graphs
- On weakly diamond-free Berge graphs
- Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
- The splittance of a graph
- Coloring perfect \((K_ 4\)-e)-free graphs
- A reduction procedure for coloring perfect \(K_ 4\)-free graphs
- On Tucker vertices of graphs
- An algorithm for colouring perfect planar graphs
- Perfect colorings of the prism graph
- An exact method for graph coloring
- Colouring Some Classes of Perfect Graphs Robustly
- scientific article; zbMATH DE number 4144006 (Why is no real title available?)
- Exact Algorithms for Coloring Graphs While Avoiding Monochromatic Cycles
- scientific article; zbMATH DE number 108587 (Why is no real title available?)
- scientific article; zbMATH DE number 1033812 (Why is no real title available?)
- On word colourings and some perfect graphs
- Perfect and locally perfect colorings
This page was built for publication: An algorithm for coloring some perfect graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1382811)
