pith. sign in

arxiv: 1410.7423 · v2 · pith:FWRZUGYJnew · submitted 2014-10-27 · 🧮 math.CO

Packing odd T-joins with at most two terminals

classification 🧮 math.CO
keywords sigmajoinsterminalspackingresultsubseteqedgeseven
0
0 comments X
read the original abstract

Take a graph $G$, an edge subset $\Sigma\subseteq E(G)$, and a set of terminals $T\subseteq V(G)$ where $|T|$ is even. The triple $(G,\Sigma,T)$ is called a signed graft. A $T$-join is odd if it contains an odd number of edges from $\Sigma$. Let $\nu$ be the maximum number of edge-disjoint odd $T$-joins. A signature is a set of the form $\Sigma\triangle \delta(U)$ where $U\subseteq V(G)$ and $|U\cap T)$ is even. Let $\tau$ be the minimum cardinality a $T$-cut or a signature can achieve. Then $\nu\leq \tau$ and we say that $(G,\Sigma,T)$ packs if equality holds here. We prove that $(G,\Sigma,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.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.