Applications of the Strong Splitter Theorem

SEP 07, 2017 | 4:15 PM TO 6:00 PM

Details

WHERE:

The Graduate Center
365 Fifth Avenue

ROOM:

9204

WHEN:

September 07, 2017: 4:15 PM-6:00 PM

ADMISSION:

Free

Description

Speaker: Sandra Kingan, Brooklyn College
 
Title: Applications of the Strong Splitter Theorem
 
Abstract: The Splitter Theorem states that, if G is a simple 3-connected graph with a simple 3-connected minor H then (with some exceptions) G can be obtained from H by adding an edge between non-adjacent vertices or splitting a vertex. The Strong Splitter Theorem optimizes the Splitter Theorem to best possible. In this talk we present a decomposition result for graphs and an algorithm for constructing 3-connected graphs using the Strong Splitter Theorem and Brendan McKay's Nauty for isomorphism checking. The Splitter Theorem (P.D. Seymour, 1980, J. Comb. Theory Ser. B 28(3) 305-359) and the Strong Splitter Theorem (S.R. Kingan and M. Lemos (2014) Annals of Comb. 18(1), 111-116) are matroid results and this perspective on graphs comes from matroid theory. Portions of this talk are joint work with Robert Kingan and Manoel Lemos.