Changes

Jump to: navigation, search

Recognition of Seymour graphs

119 bytes added, 14:30, 1 June 2014
An equivalent definition of Seymour graphs is that the minimum size of a [[T-join]] equals the maximum number of edge-disjoint [[T-join|T-cuts]] for every node set ''T'' of even size. A co-NP characterization of Seymour graphs is known, see Ageev, Kostochka and Szigeti <ref name="Ag"/>. An excluded minor characterization was given by Ageev, Benchetrit, Sebő, and Szigeti <ref name="Ag2"/>.
 
==Related conjectures==
 
[http://www.openproblemgarden.org/op/packing_t_joins Packing T-joins (Open Problem Garden)]
==References==
1,595
edits