Characterizations of Non-Seymour Graphs
|Affiliation:||INP Grenoble and Ensimag|
|Room:||Mathematics and Computer Building (MC) 5136B|
A graph is called Seymour if for every join F there exists a complete packing of F-cuts. Bipartite graphs and series-parallel graphs are Seymour, by two results of Seymour, of course. Numerous equivalent characterizations of non-Seymour graphs will be presented, each of them of the form: by contracting some kind of subgraphs, a special K_4 or prism can be found.
200 University Avenue West
Waterloo, ON N2L 3G1