Noon lecture

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

On 15.12.2011 at 12:20 in S6, there is the following noon lecture:

Lift Contractions

Daniel Paulusma

Durham University

Abstract

We introduce a new containment relation in graphs: lift contractions. We say that a graph H is a lift contraction of G if H can be obtained from G by a sequence of edge lifts and edge contractions. The edge lift operation is defined as follows. Let e=uv and e'=uw be two different edges incident with the same vertex u in a graph G. The lift of e and e' removes e and e' from G and then adds the edge vw if v and w are nonadjacent. We show that a graph contains every n-vertex graph as a lift contraction, if (1) its treewidth is large enough, or (2) its pathwidth is large enough and it is 2-connected, or (3) its order is large enough and its minimum degree is at least 3.

Joint work with: Petr Golovach, Marcin Kaminski and Dimitrios Thilikos

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