Graphs that have clique (partial) 2-trees

被引：0

作者：

McKee, Terry A. ^{[1
]}

机构：

[1] Wright State Univ, Dayton, OH 45435 USA

来源：

JOURNAL OF COMBINATORICS | 2012年 / 3卷 / 04期

关键词：

Clique graph; clique tree; chordal graph; 2-tree; series-parallel;

D O I：

暂无

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

Much of the theory-and the applicability-of chordal graphs is based on their being the graphs that have clique trees. Chordal graphs can be generalized to the graphs that have clique representations that are 2-trees, or even series-parallel graphs (partial 2-trees) or outerplanar or maximal outerplanar graphs. The resulting graph classes can be characterized by forbidding contractions of a few induced subgraphs. There is also a plausible application of such graphs to systems biology.

引用

页码：623 / 632

页数：10

共 14 条

[1] Brandstadt A., 1999, GRAPH CLASSES SURVEY
[2] Buneman P., 1974, Discrete Mathematics, V9, P205, DOI 10.1016/0012-365X(74)90002-8
[3] Chartrand G., 1971, J COMB THEORY B, V10, P12
[4] COHERENT ORIENTATIONS AND SERIES-PARALLEL NETWORKS
DANTONA, O
KUNG, JPS
[J]. DISCRETE MATHEMATICS, 1980, 32 (01) : 95 - 98
[5] Gavril F., 1974, Journal of Combinatorial Theory, Series B, V16, P47, DOI 10.1016/0095-8956(74)90094-X
[6] Augmenting outerplanar graphs
Kant, G
[J]. JOURNAL OF ALGORITHMS-COGNITION INFORMATICS AND LOGIC, 1996, 21 (01): : 1 - 25
[7] Kloks T., 1994, TREEWIDTH COMPUTATIO
[8] MCKEE T, 1999, TOPICS INTERSECTION
[9] McKee T. A., 2011, ADV INTERDISCIPLINAR, P53
[10] SERIES-PARALLEL GRAPHS - A LOGICAL APPROACH
MCKEE, TA
[J]. JOURNAL OF GRAPH THEORY, 1983, 7 (02) : 177 - 181

← 1 2 →