On the structure of (P5,gem)-free graphs

被引：34

作者：

Brandstädt, A

Kratsch, D

机构：

[1] Univ Rostock, Fachbereich Informat, D-18051 Rostock, Germany

[2] Univ Metz, Lab Informat Theor & Appl, F-57045 Metz 01, France

来源：

DISCRETE APPLIED MATHEMATICS | 2005年 / 145卷 / 02期

关键词：

(P-5; gem)-free graphs; modules and homogeneous sets in graphs; prime graphs; modular decomposition; clique width;

D O I：

10.1016/j.dam.2004.01.009

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

We give a complete structure description of (P-5,gem)-free graphs. By the results of a related paper, this implies bounded clique width for this graph class. Hereby, as usual, the P5 is the induced path with five vertices a, b, c, d, e and four edges ab, bc, cd, de, and the gem consists of a P-4 a, b, c, d with edges ab, be, cd plus a universal vertex e adjacent to a, b, c, d. (C) 2004 Elsevier B.V. All rights reserved.

引用

页码：155 / 166

页数：12

共 17 条

[1]

BRANDSTADT A, 2002, UNPUB CHORDAL CO GEM

[2]

Brandstadt Andreas, 1999, SIAM MONOGRAPHS DISC, V3

[3]

Corneil D., 1984, C NUMER, V43, P249

[4] COMPLEMENT REDUCIBLE GRAPHS [J].