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

About 1 year old · traced to

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.

References

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.