|
|||||
|
|
Vertex-minor reductions can simulate edge contractions |
|
| Authors: | Mamadou Moustapha Kanté |
| Institution: | LaBRI, Université Bordeaux 1, CNRS, 351 Cours de la libération, 33405 Talence Cedex, France |
| 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: | Clique-width Rank-width Tree-width Tree-decomposition Local complementation Edge contraction Vertex-minor |
| 本文献已被 ScienceDirect 等数据库收录！ | |