Rank-width is less than or equal to branch-width

被引：31

作者：

Oum, Sang-il ^{[1
]}

机构：

[1] Georgia Inst Technol, Sch Math, Atlanta, GA 30332 USA

来源：

JOURNAL OF GRAPH THEORY | 2008年 / 57卷 / 03期

关键词：

rank-width; branch-width; tree-width; clique-width; line graphs; incidence graphs;

D O I：

10.1002/jgt.20280

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

We prove that the rank-width of the incidence graph of a graph G is either equal to or exactly one less than the branch-width of G, unless the maximum degree of G is 0 or 1. This implies that rank-width of a graph is less than or equal to branch-width of the graph unless the branch-width is 0. Moreover, this inequality is tight. (C) 2007 Wiley Periodicals, Inc.

引用

页码：239 / 244

页数：6

共 50 条

[41] Rank-width and well-quasi-ordering of skew-symmetric or symmetric matrices
Oum, Sang-il
LINEAR ALGEBRA AND ITS APPLICATIONS, 2012, 436 (07) : 2008 - 2036
[42] Dominating sets in planar graphs: Branch-width and exponential speed-up
Fomin, FV
Thilikos, DM
PROCEEDINGS OF THE FOURTEENTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, 2003, : 168 - 177
[43] Dominating sets in planar graphs: Branch-width and exponential speed-up
Fomin, Fedor V.
Thilikos, Dimitrios M.
SIAM JOURNAL ON COMPUTING, 2006, 36 (02) : 281 - 309
[44] Obstructions for matroids of path-width at most k and graphs of linear rank-width at most k
Kante, Mamadou Moustapha
Kim, Eun Jung
Kwon, O-joung
Oum, Sang-il
JOURNAL OF COMBINATORIAL THEORY SERIES B, 2023, 160 : 15 - 35
[45] Branch-width, parse trees, and monadic second-order logic for matroids
Hlineny, P
STACS 2003, PROCEEDINGS, 2003, 2607 : 319 - 330
[46] A unified approach to polynomial algorithms on graphs of bounded (bi-)rank-width
Ganian, Robert
Hlineny, Petr
Obdrzalek, Jan
EUROPEAN JOURNAL OF COMBINATORICS, 2013, 34 (03) : 680 - 701
[47] Excluded vertex-minors for graphs of linear rank-width at most k
Jeong, Jisu
Kwon, O-joung
Oum, Sang-il
EUROPEAN JOURNAL OF COMBINATORICS, 2014, 41 : 242 - 257
[48] On parse trees and Myhill-Nerode-type tools for handling graphs of bounded rank-width
Ganian, Robert
Hlineny, Petr
DISCRETE APPLIED MATHEMATICS, 2010, 158 (07) : 851 - 867
[49] Linear Rank-Width of Distance-Hereditary Graphs I. A Polynomial-Time Algorithm
Adler, Isolde
Kante, Mamadou Moustapha
Kwon, O-Joung
ALGORITHMICA, 2017, 78 (01) : 342 - 377
[50] Monoidal Width: Capturing Rank Width
Di Lavore, Elena
Sobocinski, Pawel
ELECTRONIC PROCEEDINGS IN THEORETICAL COMPUTER SCIENCE, 2023, (380): : 268 - 283

← 1 2 3 4 5 →