Daniel Paulusma
Lift Contractions
Joint work with: Petr Golovach, Marcin Kaminski and Dimitrios Thilikos
DATE: | Tuesday, February 21, 2012 |
TIME: | 11:00 |
VENUE: | Seminar Room Gödel |
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 connected 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.