Rank-width of Random Graphs

Choongbum Lee, Joonkyung Lee, Sang-il Oum

Published 2010-01-04Version 1

Rank-width of a graph G, denoted by rw(G), is a width parameter of graphs introduced by Oum and Seymour (2006). We investigate the asymptotic behavior of rank-width of a random graph G(n,p). We show that, asymptotically almost surely, (i) if 0<p<1 is a constant, then rw(G(n,p)) = \lceil n/3 \rceil-O(1), (ii) if 1/n<< p <1/2, then rw(G(n,p))= \lceil n/3\rceil-o(n), (iii) if p = c/n and c > 1, then rw(G(n,p)) > r n for some r = r(c), and (iv) if p <= c/n and c<1, then rw(G(n,p)) <=2. As a corollary, we deduce that G(n,p) has linear tree-width whenever p=c/n for each c>1, answering a question of Gao (2006).