{"id":"arxiv/2602.03016","url":"https://arxiv.org/abs/2602.03016","tags":["math.CO"],"score":0,"title":"A counterexample to Hickingbotham's conjecture about $k$-ghost-edges","domain":"math.CO","source":"arxiv","authors":["Rong Chen"],"reviews":0,"subject":"math.CO","summary":"Fix $k\\in \\mathbb{N}$ and let $G$ be a connected graph with $tw(G)\\leq k$. We say that $xy\\in E(G^c)$ is a {\\em $k$-ghost-edge} of $G$ if for every tree decomposition $(T,\\cB)$ of $G$ with width at most $k$, the set $\\{x,y\\}$ is contained in a bag of $(T,\\cB)$. Although a $k$-ghost-edge of $G$ is not an edge of $G$, but it behaves like real edges with respect to tree decomposition of $G$ with width at most $k$. For any graph $G$ with treewidth $k$ and $xy\\in E(G^c)$, when there are at least $k+1$ internally vertex disjoint $(x,y)$-paths, Hickingbotham proved that $xy$ is a $k$-ghost-edge of…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-02-03","reactions":{}}