Skip to main content
edited tags
Link
Victor
  • 655
  • 3
  • 11
added 310 characters in body
Source Link
Victor
  • 655
  • 3
  • 11

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.

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))$.

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.
Source Link
Victor
  • 655
  • 3
  • 11

Can graphs of bounded treewidth be covered by two graphs of bounded pathwidth?

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))$.