<p>I think there is no simpler characterization than just the fact that the treewidth of <span class="math-container">$G$</span> 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.</p>

CC BY-SA 4.0
2021-01-04T09:28:22.620Z
2021-01-04T09:28:22.620Z
Laakeri
<p>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?</p>
<p>More generally, I would like to find a property <span class="math-container">$P$</span> such that for any bipartite graph <span class="math-container">$G$</span> the following statement is true: &quot;the treewidth of <span class="math-container">$G$</span> is bound by a constant if and only if <span class="math-container">$G$</span> satisfies property <span class="math-container">$P$</span>.&quot;</p>

<graph-theory>
When does a bipartite graph have bounded treewidth?
Will
# When does a bipartite graph have bounded treewidth?

(Asked by: username_0 on 2021-01-04)

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$."

**Tags:** graph-theory


---

## 1 answers

### Answer by username_1 on 2021-01-04. Score: 7

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.


---

