# Does treewidth $k$ imply the existence of a $K_{1,k}$ minor?

Let $k$ be fixed, and let $G$ be a (connected) graph. If I'm not mistaken, it follows from the work of Bodlaender [1, Theorem 3.11] that if the treewidth of $G$ is roughly at least $2k^3$, then $G$ contains a star $K_{1,k}$ as a minor.

Can we make the term $2k^3$ smaller? That is, does say treewidth at least $k$ already imply the existence of a $K_{1,k}$-minor? Is there a proof somewhere?

• A loosely related result from Demaine and Hajiaghayi: For a fixed graph $H$, any $H$-minor-free graph of treewidth $w$ has an $\Omega(w) \times \Omega(w)$ grid graph minor.
– mhum
Jun 9, 2015 at 22:28
• @mhum the constant in the $\Omega$ depends exponentially on $|H|$, so directly applying this will give a worse than $2k^3$ bound. Jun 9, 2015 at 23:00
• @daniello That is indeed the case. The constant is not very nice and the specialization to $H$-minor-free graphs is also not great. I just wanted to point out a vaguely related result.
– mhum
Jun 9, 2015 at 23:20

It is indeed true that every graph $G$ with no $K_{1,k}$ minor has treewidth at most $k-1$. We prove this below, first a few definitions:

Let $tw(G)$ be the treewidth of $G$ and $\omega(G)$ be the maximum size of a clique in $G$. A graph $H$ is a triangulation of $G$ if $G$ is a subgraph of $H$ and $H$ is chordal (i.e has no induced cycles on at least $4$ vertices). A triangulation $H$ of $G$ is a minimal triangulation if no proper subgraph of $H$ is also a triangulation of $G$. A subset $X$ of vertices of $G$ is a potential maximal clique if there exists a minimal triangulation $H$ of $G$ such that $X$ is a maximal clique of $H$. It is well known that $$tw(G) = \min_{H} \omega(H) - 1$$ Here, the minimum is taken over all minimal triangulations $H$ of $G$.

The above formula implies that to prove that $tw(G) \leq k-1$ it is sufficient to prove that all potential maximal cliques of $G$ have size at most $k$. We now prove this. Let $X$ be a potential maximal clique of $G$, and suppose that $|X| \geq k+1$.

We will use the following characterization of potential maximal cliques: a vertex set $X$ is a potential maximal clique in $G$ if, and only if, for every pair $u$, $v$ of non-adjacent (distinct) vertices in $X$ there is a path $P_{u,v}$ from $u$ to $v$ in $G$ with all its internal vertices outside of $X$. This characterization can be found in the paper Treewidth and Minimum Fill-in: Grouping the Minimal Separators by Bouchitte and Todinca.

With this characterization it is easy to derive a $K_{1,k}$ minor from $X$. Let $u \in X$. For every vertex $v \in X \setminus \{u\}$, either $uv$ is an edge of $G$ or there is a path $P_{u,v}$ from $u$ to $v$ with all internal vertices outside $X$. For all $v \in X$ that are non-adjacent to $u$ contract all the internal vertices of $P_{u,v}$ into $u$. We end up with a minor of $G$ in which $u$ is adjacent to all of $X$, and $|X| \geq k+1$. So the degree of $u$ in this minor is at least $k$, completing the proof.

• Thank you Daniel! Do you happen to know if the same argument (or result, really) has been published somewhere?
– Juho
Jun 10, 2015 at 13:29
• I don't have a reference, but I seem to remember that a similar looking (possibly less tight) argument for $K_{2,r}$ free graphs is written somewhere. Unfortunately I don't have a more concrete pointer. Jun 10, 2015 at 19:23