Bounded queue-number for layered treewidth graphs
Open problem on queue-number of bounded layered treewidth graphs · arXiv:1810.08314
Status open high confidence
No resolution of the conjecture has been found in the published literature. Dujmović et al. (arXiv:1810.08314) proved an O(k log n) upper bound on queue-number for n-vertex graphs of layered treewidth k, and the question of a constant bound remains open. A subsequent paper (arXiv:2105.01230) establishes a structural reduction showing that bounded layered treewidth implies bounded queue-number if and only if layered treewidth 1 graphs have bounded queue-number, but does not resolve the conjecture. No proof or disproof was found across targeted searches covering literature through 2025.
Cited literature (1)
-
Proves an equivalence: graphs of bounded layered treewidth have bounded queue-number if and only if graphs of layered treewidth 1 have bounded queue-number, reducing the open problem to its simplest special case without resolving it.
Reviewer notes. No proof or disproof of the conjecture was found across multiple targeted searches. The paper arXiv:2105.01230 reduces the problem to the special case of layered treewidth 1 but leaves the main question open. The O(k log n) upper bound by Dujmović et al. remains the best known result.
Context
Dujmović et al. proved that every $n$-vertex graph with layered treewidth $k$ has queue-number $O(k \log n)$. Subsequent to the submission of this paper, improved bounds on queue-number were obtained, but the question of whether a constant bound holds for graphs of bounded layered treewidth remains open.
Notes. Stated in a footnote without a formal labeled environment.
Source paper
Minor-closed graph classes with bounded layered pathwidth
Vida Dujmović, David Eppstein, Gwenaël Joret, Pat Morin, David R. Wood · 2020-06-04
https://arxiv.org/abs/1810.08314
PDF source