5
$\begingroup$

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.

$\endgroup$

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.