More forbidden minors for wye-delta-wye reducibility (Q813923)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: More forbidden minors for wye-delta-wye reducibility |
scientific article; zbMATH DE number 5002940
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | More forbidden minors for wye-delta-wye reducibility |
scientific article; zbMATH DE number 5002940 |
Statements
More forbidden minors for wye-delta-wye reducibility (English)
0 references
31 January 2006
0 references
Summary: A graph is \(Y\Delta Y\) reducible if it can be reduced to isolated vertices by a sequence of series-parallel reductions and \(Y \Delta Y\) transformations. It is still an open problem to characterize \(Y \Delta Y\) reducible graphs in terms of a finite set of forbidden minors. We obtain a characterization of such forbidden minors that can be written as clique \(k\)-sums for \(k=1,2,3\). As a result we show constructively that the total number of forbidden minors is more than 68 billion up to isomorphism.
0 references
series-parallel reductions
0 references
transformations
0 references
characterization
0 references
