Gajarsky–Pilipczuk–Toruńczyk conjecture on cliquewidth obstruction classes via walls

For a graph class C\mathscr{C}, write C\mathscr{C} transduces a class D\mathscr{D} 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 C\mathscr{C} has unbounded cliquewidth if and only if C\mathscr{C} transduces a class D\mathscr{D} 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

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.