The c-pathwidth lower-bound conjecture
The c-pathwidth lower-bound conjecture
Let be a positive integer. For a graph , write - for its -pathwidth, for its treewidth, and for the number of vertices of . The c-pathwidth lower-bound conjecture. There is a constant and a class of graphs of unbounded treewidth such that, for every ,
The source presents this as an extension of the lower bound in Proposition from ordinary pathwidth to -pathwidth. Whether -pathwidth can be bounded above by a function of treewidth alone is stated to be unknown, and the conjectured lower bound would show a strong separation on a class of graphs with unbounded treewidth.
Sources & referencesView supporting material
Primary source
Igor Razgon, “The splitting power of branching programs of bounded repetition and CNFs of bounded width”, arXiv:2201.02173 (2022).
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.