An algorithm for coloring some perfect graphs
type: Item
instance of: scholarly article
title: An algorithm for coloring some perfect graphs
zbMATH Open document ID: 0895.05023
DOI: 10.1016/S0012-365X(97)00082-4
author: Sylvain Gravier
author: Frédéric Maffray
author: Hacène Ait Haddadene
published in: Discrete Mathematics
publication date: 1998-09-14T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 05C85
zbMATH DE Number: 1130761
zbMATH Keywords: chromatic number
zbMATH Keywords: colouring
zbMATH Keywords: colouring algorithm
zbMATH Keywords: perfect graphs
reviewed by: Timothy R. S. Walsh
MaRDI profile type: Publication
cites work: Q3286847
cites work: On rigid circuit graphs
cites work: Q3328583
cites work: Q3216686
cites work: On weakly diamond-free Berge graphs
cites work: The splittance of a graph
cites work: Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
cites work: Coloring perfect \((K_ 4\)-e)-free graphs
cites work: A reduction procedure for coloring perfect \(K_ 4\)-free graphs
Recommended article: Precoloring Extension III: Classes of Perfect Graphs
Recommended article: Coloring perfect \((K_ 4\)-e)-free graphs
Recommended article: A reduction procedure for coloring perfect \(K_ 4\)-free graphs
Recommended article: On-line coloring of perfect graphs
Recommended article: Q4635984
Recommended article: Q4024059
Recommended article: Q3351379
Recommended article: Q3337488
Recommended article: Perfectly colorable graphs
Recommended article: Efficient parallel and sequential algorithms for 4-coloring perfect planar graphs
description: scientific article; zbMATH DE number 1130761