MSO obstruction characterization for bounded linear cliquewidth

Let C\mathscr{C} be a class of graphs. A class is bounded linear cliquewidth when its linear cliquewidth is bounded, and CMSO\mathsf{CMSO} denotes counting monadic second-order logic.

Linear cliquewidth CMSO obstruction conjecture. A class of graphs C\mathscr{C} has bounded linear cliquewidth if and only if the class of trees cannot be CMSO\mathsf{CMSO}-transduced from C\mathscr{C}.

The analogous characterization for cliquewidth is known with the class of all graphs in place of trees, but the linear-cliquewidth version remains open according to the survey.

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.