×

More forbidden minors for wye-delta-wye reducibility. (English) Zbl 1080.05080

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.

MSC:

05C75 Structural characterization of families of graphs
05C83 Graph minors

Software:

nauty