Current browse context:
math.CO
Change to browse by:
References & Citations
Mathematics > Combinatorics
Title: Snakes and Ladders: a Treewidth Story
(Submitted on 21 Feb 2023 (v1), last revised 30 Jan 2024 (this version, v2))
Abstract: Let $G$ be an undirected graph. We say that $G$ contains a ladder of length $k$ if the $2 \times (k+1)$ grid graph is an induced subgraph of $G$ that is only connected to the rest of $G$ via its four cornerpoints. We prove that if all the ladders contained in $G$ are reduced to length 4, the treewidth remains unchanged (and that this bound is tight). Our result indicates that, when computing the treewidth of a graph, long ladders can simply be reduced, and that minimal forbidden minors for bounded treewidth graphs cannot contain long ladders. Our result also settles an open problem from algorithmic phylogenetics: the common chain reduction rule, used to simplify the comparison of two evolutionary trees, is treewidth-preserving in the display graph of the two trees.
Submission history
From: Steven Kelk [view email][v1] Tue, 21 Feb 2023 13:25:05 GMT (323kb,D)
[v2] Tue, 30 Jan 2024 10:49:47 GMT (306kb,D)
Link back to: arXiv, form interface, contact.