Twin-width vs Queue Number Separation
Open Problem (separating twin-width and queue number on sparse graphs) · arXiv:2204.12330
Status open high confidence
The problem of separating twin-width and queue number on sparse graphs (or groups) remains open as of 2026. It is known that finite queue number implies finite twin-width, but no example of a group or sparse graph with finite twin-width and infinite queue number has been found. While a separation between sparse twin-width and stack number exists, the analogous question for queue number is unresolved, and recent papers on sparse twin-width (2023–2024) do not address this problem.
Reviewer notes. No follow-up paper resolving this open problem was found in the indexed literature. Three web searches and two WebFetch calls returned no evidence of a separation or a proof of equivalence between twin-width and queue number on sparse graphs. The problem is stated informally (not as a numbered conjecture) in 2204.12330, and the only known direction is that bounded queue number implies bounded twin-width.
Context
Finite queue number implies finite twin-width, so the two parameters are not equivalent in general. However, no example of a group (or sparse graph) with finite twin-width and infinite queue number is known, and the same gap exists for the corresponding uniform variants. Many results of the paper hold simultaneously for both parameters, making a separation elusive.
Notes. Explicitly declared an open problem in Section 1.4.
Source paper
Twin-width VII: groups
Édouard Bonnet, Colin Geniet, Romain Tessera, Stéphan Thomassé · 2022-07-15
https://arxiv.org/abs/2204.12330
PDF source