A graph is $Y \Delta Y$-reducible if it can be reduced to an empty graph by the following operations:

  • $Y \leftrightarrow\Delta$ transforms;
  • Replacing multiple edges with single edges (parallel reduction);
  • Contracting an edge, provided that at least one endpoint has degree at most $2$ (series reduction).
  • Removal of loops.

It has been shown that a minor of a $Y \Delta Y$-reducible graph is also $Y \Delta Y$-reducible. Hence, by the Robertson-Seymour theorem, there is a finite obstruction set of 'forbidden minors', which includes the seven graphs of the Petersen family.

In $2006$, Yaming Yu proved that there are at least $68897913659$ forbidden minors, and mentions that it is an open problem whether there are more.

I ask for an upper bound on the number of forbidden minors. The strength of the Robertson-Seymour theorem suggests that this could be incredibly large.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.