Skip to main content
eScholarship
Open Access Publications from the University of California

More forbidden minors for Wye-Delta-Wye reducibily

Creative Commons Attribution 4.0 International Public License
Abstract

A graph is Y Delta Y reducible if it can be reduced to isolate vertices by a sequence of series-parallel reductions and Y Delta Y transformations. It is still an open problem to characterize 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 kappa-sums for kappa = 1, 2, 3. As a result we show constructively that the total number of forbidden minors is more than 68 billion up to isomorphism.

Many UC-authored scholarly publications are freely available on this site because of the UC Academic Senate's Open Access Policy. Let us know how this access is important for you.

Main Content
Current View