Summary: Rank-width is a graph width parameter introduced by S.-I. Oum and P. Seymour [“Approximating clique-width and branch-width”, J. Comb. Theory, Ser. B 96, No. 4, 514–528 (2006; Zbl 1114.05022)]. It is known that a class of graphs has bounded rank-width if and only if it has bounded clique-width, and that the rank-width of \(G\) is less than or equal to its branch-width. The \(n\times n\) square grid, denoted by \(G _{n,n }\), is a graph on the vertex set \(\{1,2,\dotsc,n\}\times\{1,2,\dotsc,n\}\), where a vertex \((x,y)\) is connected by an edge to a vertex \((x',y')\) if and only if \(| x - x'| + | y - y'| = 1\). We prove that the rank-width of \(G _{n,n }\) is equal to \(n - 1\), thus solving an open problem of Oum.
For the entire collection see [Zbl 1153.68002].