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

1 Answer 1

7
$\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 and acknowledge you have read our privacy policy.

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