Tree- and forest-perfect graphs

被引：5

作者：

Brandstädt, A ^{[1
]}

Le, VB ^{[1
]}

机构：

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

来源：

DISCRETE APPLIED MATHEMATICS | 1999年 / 95卷 / 1-3期

关键词：

perfect graphs; P-4-structure of perfect graphs; graphs with P-4-structure of trees; characterization; linear time recognition;

D O I：

10.1016/S0166-218X(99)00071-2

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

Two graphs G and H with the same vertex set V are P-4-isomorphic if there exists a permutation pi on V such that, for all subsets S subset of or equal to V, S induces a chordless path on four vertices (denoted by P-4) in G if and only if pi(S) induces a P-4 in H. This paper gives a classification of all graphs P-4-isomorphic to a tree, respectively, a forest. (C) 1999 Elsevier Science B.V. All rights reserved.

引用

页码：141 / 162

页数：22

共 20 条

[1]

BABEL L, IN PRESS DISCRETE AP

[2]

BABEL L, 1997, THESIS TU MUNCHEN GE

[3]

BERGE C, 1984, ANN DISCRETE MATH, V21

[4]

BRANDSTADT A, IN PRESS GRAPHS COMB

[5]

BRANDSTADT A, IN PRESS DISCRETE AP

[6]

BRANDSTADT A, 1996, 1996 RRR RUTG U

[7]

Chvatal V., 1984, ANN DISCRETE MATH, V88, P279

[8] A LINEAR RECOGNITION ALGORITHM FOR COGRAPHS [J].

CORNEIL, DG ;

PERL, Y ;

STEWART, LK .

SIAM JOURNAL ON COMPUTING, 1985, 14 (04) :926-934

[9]

Cournier A., 1994, LECT NOTES COMPUTER, V787, P68

[10] RECOGNIZING THE P(4)-STRUCTURE OF A TREE [J].

DING, G .

GRAPHS AND COMBINATORICS, 1994, 10 (04) :323-328

← 1 2 →