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.
