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.
References
- Michał Pilipczuk, “Graph classes through the lens of logic”, arXiv:2501.04166 (2025).
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.