Rank-width and vertex-minors
Rank-width and vertex-minors
复制标题
等级宽度和次要顶点
DOI：
10.1016/j.jctb.2005.03.003
复制
发表时间：
2005
期刊：
影响因子：
--
通讯作者：
Sang
中科院分区：
文献类型：
--
作者：
Sang
排名宽度是一个图形参数，与固定函数相关，但更容易处理。 Clique-width 具有很好的算法属性，但没有类似于树宽度的图次要嵌入的良好“次要”关系。在本文中，我们讨论图的顶点次关系及其与秩宽度的联系。我们证明了二分图的顶点次要与二元拟阵的次要之间的关系，并且作为一个应用，我们证明了足够大的秩宽度的二分图包含某些二分图作为顶点次要。本文的主要定理是，对于固定的 k，存在一个有限的图列表，使得图 G 的秩宽度最多为 k 当且仅当列表中没有图与 G 的小顶点同构时。此外，我们证明图的秩宽度最多为 1 当且仅当它是距离遗传的。
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 1 if and only if it is distance-hereditary.