12
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ 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. $\endgroup$ – mhum Jun 9 '15 at 22:28
  • 1
    $\begingroup$ @mhum the constant in the $\Omega$ depends exponentially on $|H|$, so directly applying this will give a worse than $2k^3$ bound. $\endgroup$ – daniello Jun 9 '15 at 23:00
  • $\begingroup$ @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. $\endgroup$ – mhum Jun 9 '15 at 23:20
15
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thank you Daniel! Do you happen to know if the same argument (or result, really) has been published somewhere? $\endgroup$ – Juho Jun 10 '15 at 13:29
  • $\begingroup$ 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. $\endgroup$ – daniello Jun 10 '15 at 19:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.