Recognition of Seymour graphs
A graph G is said to be a Seymour graph if for any edge set F that satisfies [math]|C\cap F|\le |C\setminus F|[/math] for every circuit C of G, there exist [math]|F|[/math] pairwise disjoint cuts each containing exactly one element of F. Can we decide in polynomial time whether a graph is Seymour?
An equivalent definition of Seymour graphs is that the minimum size of a T-join equals the maximum number of edge-disjoint T-cuts for every node set T of even size. A co-NP characterization of Seymour graphs is known, see Ageev, Kostochka and Szigeti . An excluded minor characterization was given by Ageev, Benchetrit, Sebő, and Szigeti .