Rank‐width is less than or equal to branch‐width |
| |
| Authors: | Sang‐il Oum |
| |
| Institution: | School of Mathematics Georgia Institute of Technology Atlanta, Georgia 30332, USA |
| |
| 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 |
| |
| Keywords: | rank‐width branch‐width tree‐width clique‐width line graphs incidence graphs |
|
|
