2014/10/27 by Abdi, Ahmad, Guenin, Bertrand
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.1410.7423
Take a graph G, an edge subset Σ⊆ E(G), and a set of terminals T⊆ V(G) where |T| is even. The triple (G,Σ,T) is called a signed graft. A T-join is odd if it contains an odd number of edges from Σ. Let ν be the maximum number of edge-disjoint odd T-joins. A signature is a set of the form Σ\triangle δ(U) where U⊆ V(G) and |U∩ T) is even. Let τ be the minimum cardinality a T-cut or a signature can achieve. Then ν≤ τ and we say that (G,Σ,T) packs if equality holds here. We prove that (G,Σ,T) packs if the signed graft is Eulerian and it excludes two special non-packing minors. Our result confirms the Cycling Conjecture for the class of clutters of odd T-joins with at most two terminals. Corollaries of this result include, the characterizations of weakly and evenly bipartite graphs, packing two-commodity paths, packing T-joins with at most four terminals, and a new result on covering edges with cuts.