Local Tree-Width, Excluded Minors, and Approximation Algorithms

Hadwiger’s conjecture, among the most famous open problems in graph theory, states that every graph that does not contain K t as a minor is properly ( t − 1 )-colorable.

The purpose of this work is to demonstrate that a natural extension of ...

We prove that every graph of rank-width k is a pivot-minor of a graph of tree-width at most 2k. We also prove that graphs of rank-width at most 1, equivalently distance-hereditary graphs, are exactly vertex-minors of trees, and graphs of linear rank-...

We give the first linear kernels for the Dominating Set and Connected Dominating Set problems on graphs excluding a fixed graph H as a topological minor. In other words, we prove the existence of polynomial time algorithms that, for a given H-...