Bannister–Oudot subdivision conjecture for stack-number
Bannister–Oudot subdivision conjecture for stack-number
Let be a graph, let be an integer, and let be any -subdivision of , obtained by replacing each edge of by an internally disjoint path with at most internal vertices. Write for the stack-number of . Bannister–Oudot subdivision conjecture. There exists a function such that
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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.