Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It only takes a minute to sign up.
Sign up to join this community
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$."
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.
