# Recognition of Seymour graphs

A graph G is said to be a Seymour graph if for any edge set F that satisfies $|C\cap F|\le |C\setminus F|$ for every circuit C of G, there exist $|F|$ pairwise disjoint cuts each containing exactly one element of F. Can we decide in polynomial time whether a graph is Seymour?

## Remarks

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 [1]. An excluded minor characterization was given by Ageev, Benchetrit, Sebő, and Szigeti [2].

## References

1. A. Ageev, A. Kostochka, Z. Szigeti, A Characterization of Seymour Graphs, Journal of Graph Theory, 24/4 (1997), 357-364. DOI link, Author link.
2. A. Ageev, Y. Benchetrit, A. Sebő, Z. Szigeti, An Excluded Minor Characterization of Seymour Graphs, DOI link.