Friday, October 24, 2014 3:30 pm
-
3:30 pm
EDT (GMT -04:00)
Characterizations of Non-Seymour Graphs
Speaker: | Zoltan Szigeti |
---|---|
Affiliation: | INP Grenoble and Ensimag |
Room: | Mathematics and Computer Building (MC) 5136B |
Abstract:
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.