Treewidth of Erdős-Rényi random graphs, random intersection graphs, and scale-free random graphs

We study conditions under which the treewidth of three different classes of random graphs is linear in the number of vertices. For the Erdős-Rényi random graph G(n,m), our result improves a previous lower bound obtained by Kloks (1994) [22]. For random intersection graphs, our result strengthens a previous observation on the treewidth by Karoński et al. (1999) [19]. For scale-free random graphs based on the Barabási-Albert preferential-attachment model, it is shown that if more than 11 vertices are attached to a new vertex, then the treewidth of the obtained network is linear in the size of the network with high probability.