*********************************** * Princeton Discrete Math Seminar * *********************************** Date: Thursday 28th March, 4:30 in Fine Hall 224. Speaker: Tony Huynh (Simon Fraser) Title: Even-cycle decompositions of graphs with no odd-K_4-minor 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). ----------- Next week: TBA Anyone wishing to be added to or removed from this mailing list should contact Paul Seymour (pds@math.princeton.edu)