On algorithms for (P-5,gem)-free graphs
A graph is (P-5,gem)-free, when it does not contain P-5 (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-4) as an induced subgraph. We present O(n(2)) time recognition algorithms for chordal gem-free graphs and for (P-5,gem)-free graphs. Using a characterization of (P-5,gem)-free graphs by their prime graphs with respect to modular decomposition and their modular decomposition trees [A. Brandstadt, D. Kratsch, On the structure of (P-5,gem)-free graphs, Discrete Appl. Math. 145 (2005), 155-166], we give linear time algorithms for the following NP-complete problems on (P-5,gem)-free graphs: Minimum Coloring; Maximum Weight Stable Set; Maximum Weight Clique; and Minimum Clique Cover. (c) 2005 Elsevier B.V. All rights reserved.
recognition algorithms modular decomposition coloring clique clique cover (p(5,)gem)-free graphs independent set