Bounded cliquewidth under proper separator decompositions
Bounded cliquewidth under proper separator decompositions
Let and be classes of graphs closed under taking induced subgraphs. Suppose that every 2-connected graph in is either in or has a proper 2-separator or a proper -separator. Assume that, for some constant , every graph in has cliquewidth at most .
Cliquewidth preservation conjecture. There is a function such that every graph in has cliquewidth at most .
This conjecture asks whether decomposing graphs along proper 2-separators and proper -separators preserves bounded cliquewidth. Its status is not resolved in the supplied source.
Sources & referencesView supporting material
Primary source
Beatriz Martins and Nicolas Trotignon, “(Even hole, triangle)-free graphs revisited”, arXiv:2604.01816 (2026).
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.