# Recognition of Seymour graphs

From Egres Open

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?

## 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]}.

## Related conjectures

Packing T-joins (Open Problem Garden)

## References

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