Noon lecture

list of noon lectures ( 2005 | 2006 | 2007 | 2008 | 2009 | 2010 | 2011 | 2012 | 2013 | 2014 | 2015 | 2016 | 2017 | future lectures)

On 12.05.2011 at 12:20 in S1, there is the following noon lecture:

3-Connected Minor-Minimal Non-Projective Planar Graphs with an Internal 3-Separation

Luke Postle

Georgia Tech

Abstract

The property that a graph has an embedding in projective plane is closed under taking minors. By the well known theorem of Robertson and Seymour, there exists a finite list of minor-minimal graphs, call it L, such that a given graph G is projective planar if and only if G does not contain any graph isomorphic to a member of L as a minor. Glover, Huneke and Wang found 35 graphs in L, and Archdeacon proved that those are all the members of L. In this talk we show a new strategy for finding the list L.

Our approach is based on conditioning on the connectivity of a member of L. Assume G is a member of L. If G is not 3-connected then the G is a 0-,1-, or 2-sum of Kuratowski graphs (K_5 and K_{3,3}). In the case that G is 3-connected, the problem breaks down into two main cases, either G has an internal separation of order three or G is internally 4-connected. In this talk, we

list of noon lectures ( 2005 | 2006 | 2007 | 2008 | 2009 | 2010 | 2011 | 2012 | 2013 | 2014 | 2015 | 2016 | 2017 | future lectures)

Webmaster: kamweb.mff.cuni.cz         Modified: 19. 10. 2010