ALCOMFT-TR-03-189

Andreas Brandstädt, Hans L. Bodlaender, Dieter Kratsch, Micha\"el Rao and Jeremy Spinrad
On Algorithms for (P₅,Gem)-Free Graphs
Utrecht. Work package 2. December 2003.

Abstract: A graph is (P₅,gem)-free, when it does not contain P₅ (an induced path with five vertices) or a gem (a graph formed by making an universal vertex adjacent to each of the four vertices of the induced path P₄) as an induced subgraph.

We present O(n²) time recognition algorithms for chordal gem-free and for (P₅,gem)-free graphs. Using a characterization of (P₅,gem)-free graphs by their prime graphs with respect to modular decomposition and their modular decomposition trees [BraKra2002/1], we give linear time algorithms for the following NP-complete problems on (P₅,gem)-free graphs: Minimum Coloring, Maximum Weight Stable Set, Maximum Weight Clique, and Minimum Clique Cover.

Postscript file: ALCOMFT-TR-03-189.ps.gz (147 kb).