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

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. (C) 2007 Wiley Periodicals, Inc.