More forbidden minors for wye-delta-wye reducibility (Q813923)

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.