<p>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:</p>

<p>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 <em>potential maximal clique</em> 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$.</p>

<p>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$. </p>

<p>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 <a href="http://epubs.siam.org/doi/abs/10.1137/S0097539799359683">Treewidth and Minimum Fill-in: Grouping the Minimal Separators</a> by Bouchitte and Todinca.</p>

<p>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. </p>

CC BY-SA 3.0
2015-06-10T13:29:00.047Z
Thank you Daniel! Do you happen to know if the same argument (or result, really) has been published somewhere?
Juho
CC BY-SA 3.0
2015-06-10T19:23:49.563Z
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.
daniello
CC BY-SA 3.0
2015-06-09T18:00:35.823Z
2015-06-10T09:43:42.800Z
2015-06-10T09:43:42.800Z
daniello
<p>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. </p>

<p>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?</p>

<hr>

<p>[1] <a href="http://195.134.81.187/data/courses/treewidth/1-s2.0-S0196677483710011-main.pdf">Bodlaender, H. L. (1993). On linear time minor tests with depth-first search. Journal of Algorithms, 14(1), 1-23.</a></p>

CC BY-SA 3.0
2015-06-09T22:28:44.327Z
A loosely related result from [Demaine and Hajiaghayi](http://www-math.mit.edu/~hajiagha/gridJ.pdf): For a fixed graph $H$, any $H$-minor-free graph of treewidth $w$ has an $\Omega(w) \times \Omega(w)$ grid graph minor.
mhum
CC BY-SA 3.0
2015-06-09T23:00:56.003Z
@mhum the constant in the $\Omega$ depends exponentially on $|H|$, so directly applying this will give a worse than $2k^3$ bound.
daniello
CC BY-SA 3.0
2015-06-09T23:20:10.697Z
@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
<graph-theory><treewidth><graph-minor>
Does treewidth $k$ imply the existence of a $K_{1,k}$ minor?
Juho
# Does treewidth $k$ imply the existence of a $K_{1,k}$ minor?

(Asked by: username_0 on 2015-06-09)

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?

---

[1] [Bodlaender, H. L. (1993). On linear time minor tests with depth-first search. Journal of Algorithms, 14(1), 1-23.](http://195.134.81.187/data/courses/treewidth/1-s2.0-S0196677483710011-main.pdf)

**Tags:** graph-theory, treewidth, graph-minor

> **Comments:**
> **username_1**: A loosely related result from [Demaine and Hajiaghayi](http://www-math.mit.edu/~hajiagha/gridJ.pdf): For a fixed graph $H$, any $H$-minor-free graph of treewidth $w$ has an $\Omega(w) \times \Omega(w)$ grid graph minor.  
> **username_2**: @username_1 the constant in the $\Omega$ depends exponentially on $|H|$, so directly applying this will give a worse than $2k^3$ bound.  
> **username_1**: @username_2 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.  

---

## 1 answers

### Answer by username_2 on 2015-06-09. Score: 17 | Accepted answer

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](http://epubs.siam.org/doi/abs/10.1137/S0097539799359683) 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.

> **Comments:**
> **username_0**: Thank you Daniel! Do you happen to know if the same argument (or result, really) has been published somewhere?  
> **username_2**: 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.  

---

