On Algorithms for (P5,Gem)-Free Graphs

Abstract

A graph is (P5,gem)-free, when it does not contain P5 (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 P4) as an induced subgraph.

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