A characterization of Seymour graphs
Let \(G= (V,E)\) be an undirected, connected graph which may have loops and multiple edges. A pair \((G,T)\) where \(T\) is an even subset of \(V\) is called a graft, and for \(X\subseteq V\) the cut \(\delta(X)\) is called a \(T\)-cut if \(|X\cap T|\) is odd. A set \(F\subseteq E\) is called a \(T\)-join if \(T=\{v\in V\mid d_F(v)\) is odd\}. Let the maximum number of edge-disjoint \(T\)-cuts in \(G\) be denoted by \(\nu(G,T)\), the cardinality of a minimum \(T\)-join in \(G\) be denoted by \(\tau(G,T)\). It is easy to see that \(\nu(G,T)\leq \tau(G,T)\). Seymour showed that equality holds for bipartite and series-parallel graphs for every even vertex subset \(T\). Therefore a graph \(G\) is called Seymour graph if equality holds for all even subsets \(T\subseteq V(G)\). Sebö conjectured some structural properties of \(G\) not being a Seymour graph and the main result of this paper consists of Theorem 3 which gives a characterization of Seymour graphs. Four equivalent structural conditions for an undirected connected graph \(G\) are given, and one of these conditions is: \(G\) is not a Seymour graph. By this result a confirmation of the conjecture is given and already known results are implied. The extensive proof is based on many known statements, for instance, the theorems of Lovász and Sebö, and on many graph-theoretical concepts.
This page was built for publication: A characterization of Seymour graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3129829)