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 条

[1] Rank-width of random graphs
Lee, Choongbum
Lee, Joonkyung
Oum, Sang-il
JOURNAL OF GRAPH THEORY, 2012, 70 (03) : 339 - 347
[2] Approximating clique-width and branch-width
Oum, Sang-il
Seymour, Paul
JOURNAL OF COMBINATORIAL THEORY SERIES B, 2006, 96 (04) : 514 - 528
[3] Rank-width: Algorithmic and structural results
Oum, Sang-il
DISCRETE APPLIED MATHEMATICS, 2017, 231 : 15 - 24
[4] Testing branch-width
Oum, Sang-il
Seymour, Paul
JOURNAL OF COMBINATORIAL THEORY SERIES B, 2007, 97 (03) : 385 - 393
[5] On Low Rank-Width Colorings
Kwon, O-joung
Pilipczuk, Michal
Siebertz, Sebastian
GRAPH-THEORETIC CONCEPTS IN COMPUTER SCIENCE (WG 2017), 2017, 10520 : 372 - 385
[6] Approximating Rank-Width and Clique-Width Quickly
Oum, Sang-Il
ACM TRANSACTIONS ON ALGORITHMS, 2008, 5 (01)
[7] Rank-width and vertex-minors
Oum, SI
JOURNAL OF COMBINATORIAL THEORY SERIES B, 2005, 95 (01) : 79 - 100
[8] Computing rank-width exactly
Oum, Sang-il
INFORMATION PROCESSING LETTERS, 2009, 109 (13) : 745 - 748
[9] The Rank-Width of Edge-Coloured Graphs
Kante, Mamadou Moustapha
Rao, Michael
THEORY OF COMPUTING SYSTEMS, 2013, 52 (04) : 599 - 644
[10] Graph operations characterizing rank-width
Courcelle, Bruno
Kante, Mamadou Moustapha
DISCRETE APPLIED MATHEMATICS, 2009, 157 (04) : 627 - 640

← 1 2 3 4 5 →