Graphs that have clique (partial) 2-trees

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.

Keywords

clique graph, clique tree, chordal graph, 2-tree, series-parallel

2010 Mathematics Subject Classification

Primary 05C62. Secondary 05C75, 05C90.

Full Text (PDF format)

Published 21 February 2013