More Forbidden Minors for Wye-Delta-Wye Reducibility

  • Yaming Yu

Abstract

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.

Published
2006-01-25
Article Number
R7