MSO obstruction characterization for bounded linear cliquewidth
MSO obstruction characterization for bounded linear cliquewidth
Let be a class of graphs. A class is bounded linear cliquewidth when its linear cliquewidth is bounded, and denotes counting monadic second-order logic.
Linear cliquewidth CMSO obstruction conjecture. A class of graphs has bounded linear cliquewidth if and only if the class of trees cannot be -transduced from .
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
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.