Compute the treewidth of $K_{m,n}$ if we know that $$tw(G)=\min \{\omega(H)-1 : G\subseteq H \ \wedge \ H \ \text{is chordal}\}$$
I know it should be $\min\{m,n\}$ but I do not know how to construct the chordal graph. I mean in $K_{m,n}$ I have $4-$ and $6-$cycles. I mean, by hand it would be a lot of computing. Is there a trick on how to do this?
Let $1\le m\le n$ and the bipartition of the graph $G=K_{m,n}$ consists of $m$ red vertices and $n$ blue vertices.
Let $H$ be the graph with added edges between all pairs of red vertices. The graph $H$ is chordal because it has the following perfect elimination scheme (see, for instance, p.99 in the slides of a lecture “Colorings, Cliques and Independent Sets” by Joachim Spoerhase and Alexander Wolff). First we remove all blue vertices in any order and next all red vertices in any order. Since any maximal clique of $H$ consists of all red vertices and one blue vertex, $\omega(H)=m+1$.
On the other hand, let $H’$ be a chordal graph containing $G$. I claim that either a subgraph $K’_m$ of $G$ induced on all red vertices of $H’$ is complete, or a subgraph $K’_n$ of $G$ induced on all blue vertices of $H’$ is complete. Indeed, if this doesn’t hold then there exist two non-adjacent red vertices $v_1$ and $v_2$ and two non-adjacent blue vertices $u_1$ and $u_2$. But then $v_1-u_1-v_2-u_2-v_1$ is a chordless cycle of $H’$ of length $4$, a contradiction. If the graph $K’_m$ is complete then $H$ contains a graph $H$ from the previous paragraph. So $\omega(H)\ge \omega(H’)=m+1$. If the graph $K’_n$ then we similarly show that $\omega(H)\ge n+1$. Anyway, $\omega(H)\ge m+1$.