Bounded cliquewidth under proper separator decompositions

Let C\mathcal C and B\mathcal B be classes of graphs closed under taking induced subgraphs. Suppose that every 2-connected graph in C\mathcal C is either in B\mathcal B or has a proper 2-separator or a proper P3P_3-separator. Assume that, for some constant aa, every graph in B\mathcal B has cliquewidth at most aa.

Cliquewidth preservation conjecture. There is a function ff such that every graph in C\mathcal C has cliquewidth at most f(a)f(a).

This conjecture asks whether decomposing graphs along proper 2-separators and proper P3P_3-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

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.