{"id":"arxiv/2605.01685","url":"https://arxiv.org/abs/2605.01685","tags":["math.CO"],"score":0,"title":"On tree decompositions whose trees are subgraphs","domain":"math.CO","source":"arxiv","authors":["Rong Chen","Enzi Liao"],"reviews":0,"subject":"math.CO","summary":"Fix $k \\in \\mathbb{N}$ and let $G$ be a connected graph with treewidth at most $k$. We say that $xy \\notin E(G)$ is a {\\em $k$-ghost-edge} of $G$ if for every tree decomposition $(T, \\cB)$ of $G$ with width at most $k$, both $x$ and $y$ are contained in a bag of $(T, \\cB)$. Moreover, if $G$ does not contain any $k$-ghost-edges, then $G$ is {\\em $k$-ghost-free}. Hickingbotham proposed a conjecture that every connected $k$-ghost-free graph $G$ has a tree decomposition $(T, \\cB)$ with width at most $k$ such that $T$ is a subgraph of $G$. In this paper, we prove that Hickingbotham's conjecture…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-05-03","reactions":{}}