Vertex-minor reductions can simulate edge contractions

Article ID	Journal	Published Year	Pages	File Type
420908	Discrete Applied Mathematics	2007	13 Pages	PDF

Abstract

We prove that local complementation and vertex deletion, operations from which vertex-minors are defined, can simulate edge contractions. As an application, we prove that the rank-width of a graph is linearly bounded in term of its tree-width.

Keywords

Vertex-minor edge contraction Tree-decomposition Tree-width Rank-width Local complementation clique-width

Related Topics

Physical Sciences and Engineering Computer Science Computational Theory and Mathematics

Preview

Vertex-minor reductions can simulate edge contractions

Authors

Mamadou Moustapha Kanté,