Even-cycle decompositions of graphs with no odd-K_4-minor

Even-cycle decompositions of graphs with no odd-K_4-minor

-
Tony Huynh , Simon Fraser
Fine Hall 224

A graph is ``even-cycle decomposable'' if its edge set can be partitioned into even length cycles. Evidently, every Eulerian bipartite graph is even-cycle decomposable. Seymour proved that every 2-connected loopless Eulerian planar graph with an even number of edges is even-cycle decomposable. Later, Zhang showed that $K_5$-minor-free graphs (satisfying the obvious necessary conditions) are also even-cycle decomposable. We propose a conjecture involving signed graphs which contains all of these results. Our main result is a weakened form of this conjecture. The main technical tool we use is a structure theorem for signed graphs with no odd-K_4-minor due to Lov\'{a}sz, Seymour, Schrijver, and Truemper. In this talk we will describe this structure theorem and then give a sketch of our proof. This is joint work with Sang-il Oum (KAIST) and Maryam Verdian-Rizi (KAIST).