0
$\begingroup$

As the title says, I want to know when the treewidth of a bipartite graph is bounded by a constant. What families of graphs are both bipartite and bounded treewidth?

More generally, I would like to find a property $P$ such that for any bipartite graph $G$ the following statement is true: "the treewidth of $G$ is bound by a constant if and only if $G$ satisfies property $P$."

$\endgroup$
0
6
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.