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

✍ Scribed by Sang-il Oum

• Publisher: John Wiley and Sons
• Year: 2008
• Tongue: English
• Weight: 112 KB
• Volume: 57
• Category: Article
• ISSN: 0364-9024
• DOI: 10.1002/jgt.20280

✦ Synopsis

Abstract

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. © 2007 Wiley Periodicals, Inc. J Graph Theory 57: 239–244, 2008