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

More forbidden minors for Wye-Delta-Wye reducibily

Creative Commons 'BY' version 4.0 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's open access policies. Let us know how this access is important for you.

Main Content
Current View