Premium
Forbidden subgraphs and graph decomposition
Author(s) -
Wagner Donald K.
Publication year - 1987
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.3230170109
Subject(s) - combinatorics , matroid , partial k tree , mathematics , pathwidth , decomposition , discrete mathematics , graph , outerplanar graph , chordal graph , 1 planar graph , line graph , biology , ecology
Series‐parallel graphs, outerplanar graphs, and graphs whose polygon matroids are transversal have been characterized by forbidden subgraphs. Tutte introduced a graph decomposition for nonseparable graphs. The results of this paper relate the existence of the forbidden subgraphs to properties of the decomposition. Algorithmic implications are considered.