Changes

Jump to: navigation, search

Recognition of Seymour graphs

329 bytes added, 13:16, 18 August 2011
==Remarks==
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 <refname="Ag"/>A. An excluded minor characterization was given by Ageev, A. KostochkaBenchetrit, Z. Sebő, and Szigeti, ''A Characterization of Seymour Graphs'', Journal of Graph Theory, 24/4 (1997), 357-364. [http://dx.doi.org/10.1002/(SICI)1097-0118(199704)24:4%3C357::AID-JGT8%3E3.0.CO;2-N DOI link], [http://www.g-scop.inpg.fr/~szigetiz/articles/aksz.pdf Author link].<ref name="Ag2"/ref>.
==References==
<references>
<ref name="Ag">A. Ageev, A. Kostochka, Z. Szigeti, ''A Characterization of Seymour Graphs'', Journal of Graph Theory, 24/4 (1997), 357-364. [http://dx.doi.org/10.1002/(SICI)1097-0118(199704)24:4%3C357::AID-JGT8%3E3.0.CO;2-N DOI link], [http://www.g-scop.inpg.fr/~szigetiz/articles/aksz.pdf Author link].</ref>
<referencesref name="Ag2">A. Ageev, Y. Benchetrit, A. Sebő, Z. Szigeti, ''An Excluded Minor Characterization of Seymour Graphs'', [http://dx.doi.org/10.1007/978-3-642-20807-2_1 DOI link].</ref> </references>
[[Category:Cycles and paths]]
1,595
edits