The c-pathwidth lower-bound conjecture

Let cc be a positive integer. For a graph GG, write cc-pw(G)pw(G) for its cc-pathwidth, tw(G)tw(G) for its treewidth, and nn for the number of vertices of GG. The c-pathwidth lower-bound conjecture. There is a constant αc\alpha_c and a class Gc\mathbf{G}_c of graphs of unbounded treewidth such that, for every GGcG\in\mathbf{G}_c,

c-pw(G)αctw(G)logn.c\text{-}pw(G)\geq \alpha_c\,tw(G)\log n.

The source presents this as an extension of the lower bound in Proposition from ordinary pathwidth to cc-pathwidth. Whether cc-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

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.