Rank-width and vertex-minors

Cited 92 time in webofscience Cited 0 time in scopus
  • Hit : 235
  • Download : 0
The rank-width is a graph parameter related in terms of fixed functions to clique-width but more tractable. Clique-width has nice algorithmic properties, but no good "minor" relation is known analogous to graph minor embedding for tree-width. In this paper, we discuss the vertex-minor relation of graphs and its connection with rank-width. We prove a relationship between vertex-minors of bipartite graphs and minors of binary matroids, and as an application, we prove that bipartite graphs of sufficiently large rank-width contain certain bipartite graphs as vertex-minors. The main theorem of this paper is that for fixed k, there is a finite list of graphs such that a graph G has rank-width at most k if and only if no graph in the list is isomorphic to a vertex-minor of G. Furthermore, we prove that a graph has rank-width at most I if and only if it is distance-hereditary. (C) 2005 Elsevier Inc. All rights reserved.
Publisher
ACADEMIC PRESS INC ELSEVIER SCIENCE
Issue Date
2005-09
Language
English
Article Type
Article
Keywords

GRAPH MINORS; BRANCH-WIDTH; PLANAR GRAPH; CLIQUE-WIDTH; MATROIDS; DECOMPOSITION; OBSTRUCTIONS

Citation

JOURNAL OF COMBINATORIAL THEORY SERIES B, v.95, no.1, pp.79 - 100

ISSN
0095-8956
DOI
10.1016/j.jctb.2005.03.003
URI
http://hdl.handle.net/10203/87720
Appears in Collection
MA-Journal Papers(저널논문)
Files in This Item
There are no files associated with this item.
This item is cited by other documents in WoS
⊙ Detail Information in WoSⓡ Click to see webofscience_button
⊙ Cited 92 items in WoS Click to see citing articles in records_button

qr_code

  • mendeley

    citeulike


rss_1.0 rss_2.0 atom_1.0