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 条

[21] SATISFIABILITY, BRANCH-WIDTH AND TSEITIN TAUTOLOGIES
Alekhnovich, Michael
Razborov, Alexander
COMPUTATIONAL COMPLEXITY, 2011, 20 (04) : 649 - 678
[22] The Branch-width of circular-arc
Mazoit, F
LATIN 2006: THEORETICAL INFORMATICS, 2006, 3887 : 727 - 736
[23] Linear rank-width and linear clique-width of trees
Adler, Isolde
Kante, Mamadou Moustapha
THEORETICAL COMPUTER SCIENCE, 2015, 589 : 87 - 98
[24] Directed Rank-Width and Displit Decomposition
Kante, Mamadou Moustapha
Rao, Michael
GRAPH-THEORETIC CONCEPTS IN COMPUTER SCIENCE, 2010, 5911 : 214 - +
[25] On the excluded minors for the matroids of branch-width k
Geelen, JF
Gerards, AMH
Robertson, N
Whittle, GP
JOURNAL OF COMBINATORIAL THEORY SERIES B, 2003, 88 (02) : 261 - 265
[26] Better Polynomial Algorithms on Graphs of Bounded Rank-Width
Ganian, Robert
Hlineny, Petr
COMBINATORIAL ALGORITHMS, 2009, 5874 : 266 - 277
[27] On rank-width of (diamond, even hole)-free graphs
Adler, Isolde
Le, Ngoc Khang
Mueller, Haiko
Radovanovic, Marko
Trotignon, Nicolas
Vuskovic, Kristina
DISCRETE MATHEMATICS AND THEORETICAL COMPUTER SCIENCE, 2017, 19 (01)
[28] On the Excluded Minors for Matroids of Branch-Width Three
Hlineny, Petr
ELECTRONIC JOURNAL OF COMBINATORICS, 2002, 9
[29] Obstructions for linear rank-width at most 1
Adler, Isolde
Farley, Arthur M.
Proskurowski, Andrzej
DISCRETE APPLIED MATHEMATICS, 2014, 168 : 3 - 13
[30] On NC algorithms for problems on bounded rank-width graphs
Das, Bireswar
Dasgupta, Anirban
Enduri, Murali Krishna
Reddy, I. Vinod
INFORMATION PROCESSING LETTERS, 2018, 139 : 64 - 67

← 1 2 3 4 5 →