I think there is no simpler characterization than just the fact that the treewidth of $G$ is bounded. The intuition for why is that by subdividing each edge of a graph we get a bipartite graph with the same treewidth. In particular, we have a very simple reduction from determining the treewidth of a graph to determining the treewidth of a bipartite graph.


Consider a graph on vertex set $V_1\cup V_2\cup V_3\cup V_4\cup \{a,b,c,d\}$ where $|V_1|=|V_2|=|V_3|=|V_4|=n$. The edge set $E$ is covered by $C=\{V_1\cup\{a,c\},V_2\cup\{a,d\},V_3\cup\{b,c\},V_4\cup\{b,d\},\{a,b\},\{c,d\}\}$. When $n$ is large enough, any minimalist cover must contain the four maximum cliques $V_1\cup\{a,c\}$ and so on, so it is not hard ...


I see this question only 2.5 years after, but I think I have a relevant answer. Indeed, it is at the core of the work we have done on Fast generation of random connected graphs with prescribed degrees. In this paper, we start with a connected graph, and perform large numbers of edge swaps in order to make it random. We however want to obtain a random ...

Only top voted, non community-wiki answers of a minimum length are eligible