Bannister–Oudot subdivision conjecture for stack-number

Let GG be a graph, let kk be an integer, and let GG' be any (k)(\leqslant k)-subdivision of GG, obtained by replacing each edge of GG by an internally disjoint path with at most kk internal vertices. Write sn(G)\operatorname{sn}(G) for the stack-number of GG. Bannister–Oudot subdivision conjecture. There exists a function ff such that

sn(G)f(sn(G),k).\operatorname{sn}(G) \leqslant f(\operatorname{sn}(G'),k).

The conjecture asserts that bounded-length subdivisions cannot reduce stack-number without a corresponding bound on the original graph's stack-number. The source states that a consequence of its construction resolves this conjecture, so the conjecture is solved.

Sources & referencesView supporting material

Primary source

Vida Dujmović, David Eppstein, Robert Hickingbotham, Pat Morin and David R. Wood, “Stack-number is not bounded by queue-number”, arXiv:2011.04195 (2021).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.