On Delta‐Wye Reducibility of Toroidal Graphs

ABSTRACT In 2006, Yu proved that there are at least 68 billion forbidden minors for delta‐wye reducibility. It is an open problem to prove that this is the complete list of forbidden minors. We prove that only eight graphs from Yu's list admit an embedding in the torus. These graphs are the Petersen family of graphs together with the graph obtained from the complete bipartite graph by deleting a perfect matching. Moreover, we show that graphs that admit a toroidal embedding of representativity greater than three contain one of these eight toroidal graphs as a minor. Hence, they are not delta‐wye reducible. In contrast, we prove that any graph that admits a toroidal embedding with representativity less than two is delta‐wye reducible; in fact, 1‐terminal reducible. We also prove that if admits a toroidal embedding without disjoint essential cycles, then is delta‐wye reducible. Finally, we show that if a graph has a toroidal embedding that is a 3‐connected triangulation of the torus, then is not delta‐wye reducible.