On 15.12.2011 at 12:20 in S6, there is the following noon lecture:
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
Webmaster: kamweb.mff.cuni.cz Modified: 19. 10. 2010