Gajarsky–Pilipczuk–Toruńczyk conjecture on cliquewidth obstruction classes via walls
Gajarsky–Pilipczuk–Toruńczyk conjecture on cliquewidth obstruction classes via walls
For a graph class , write transduces a class when the class is obtainable by the relevant first-order transduction. A graph class has unbounded cliquewidth when its cliquewidth is not bounded.
Gajarsky–Pilipczuk–Toruńczyk's cliquewidth obstruction conjecture. A class of graphs has unbounded cliquewidth if and only if transduces a class that contains some subdivision of every wall.
Together with the corresponding linear-cliquewidth statement, this conjecture would characterize bounded cliquewidth through forbidden transduction patterns. The survey presents it as open.
Sources & referencesView supporting material
Primary source
Michał Pilipczuk, “Graph classes through the lens of logic”, arXiv:2501.04166 (2025).
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.