zbMATH — the first resource for mathematics

A characterization of Seymour graphs. (English) Zbl 0869.05051
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.

05C75 Structural characterization of families of graphs
Full Text: DOI