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 条

[31] On rank-width of (diamond, even hole)-free graphs
Adler I.
Le N.K.
Müller H.
Radovanović M.
Trotignon N.
Vušković K.
Discrete Math. Theor. Comput. Sci., 1
[32] Solving Problems on Graphs of High Rank-Width
Eduard Eiben
Robert Ganian
Stefan Szeider
Algorithmica, 2018, 80 : 742 - 771
[33] Better Algorithms for Satisfiability Problems for Formulas of Bounded Rank-width
Ganian, Robert
Hlineny, Petr
Obdrzalek, Jan
IARCS ANNUAL CONFERENCE ON FOUNDATIONS OF SOFTWARE TECHNOLOGY AND THEORETICAL COMPUTER SCIENCE (FSTTCS 2010), 2010, 8 : 73 - 83
[34] Graphs of small rank-width are pivot-minors of graphs of small tree-width
Kwon, O-joung
Oum, Sang-il
DISCRETE APPLIED MATHEMATICS, 2014, 168 : 108 - 118
[35] Branch-width and well-quasi-ordering in matroids and graphs
Geelen, JF
Gerards, AMH
Whittle, G
JOURNAL OF COMBINATORIAL THEORY SERIES B, 2002, 84 (02) : 270 - 290
[36] Rank-width and tree-width of H-minor-free graphs
Fomin, Fedor V.
Oum, Sang-il
Thilikos, Dimitrios M.
EUROPEAN JOURNAL OF COMBINATORICS, 2010, 31 (07) : 1617 - 1628
[37] Better Algorithms for Satisfiability Problems for Formulas of Bounded Rank-width
Ganian, Robert
Hlineny, Petr
Obdrzalek, Jan
FUNDAMENTA INFORMATICAE, 2013, 123 (01) : 59 - 76
[38] TREE PIVOT-MINORS AND LINEAR RANK-WIDTH
Dabrowski, Konrad K.
Dross, Francois
Jeong, Jisu
Kante, Mamadou M.
Kwon, O-joung
Oum, Sang-il
Paulusma, Daniel
SIAM JOURNAL ON DISCRETE MATHEMATICS, 2021, 35 (04) : 2922 - 2945
[39] Linear Rank-Width of Distance-Hereditary Graphs
Adler, Isolde
Kante, Mamadou Moustapha
Kwon, O-joung
GRAPH-THEORETIC CONCEPTS IN COMPUTER SCIENCE, 2014, 8747 : 42 - 55
[40] TREE PIVOT-MINORS AND LINEAR RANK-WIDTH
Dabrowski, K. K.
Dross, F.
Jeong, J.
Kante, M. M.
Kwon, O-J.
Oum, S-I.
Paulusma, D.
ACTA MATHEMATICA UNIVERSITATIS COMENIANAE, 2019, 88 (03): : 577 - 583

← 1 2 3 4 5 →