4
$\begingroup$

Does there exists a function $f : \mathbb{N} \rightarrow \mathbb{N}$ such that every graph $G$ of treewidth at most $k$ can be decomposed into 2 subgraphs $H_1$ and $H_2$ of pathwidth at most $f(k)$?

Decomposition here means that $G = (V(H_1) \cup V(H_2), E(H_1) \cup E(H_2))$.

UPDATE:

  1. As was observed by Tony Huynh, the question has affirmative answer for $k=1$, as every forest can be decomposed into two star-forests; for $k \geq 2$ the answer is unclear.
  2. Since every graph of treewidth $k$ is a subgraph of a $k$-tree, we can restrict consideration to $k$-trees.
Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ It's true for $k=1$, with $f(1)=1$. Every tree can be decomposed into two forests of stars, and a star has pathwidth $1$. $\endgroup$
    – Tony Huynh
    Commented Oct 18, 2016 at 18:28
  • $\begingroup$ @TonyHuynh, thanks for the observation. I forgot to mention it in the question. I'll update the question accordingly. $\endgroup$
    – Victor
    Commented Oct 18, 2016 at 18:55

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .