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.
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom