Bounded clique-width from bounded chordless-cycle subgraphs

Let GG be a graph, and let P=(A1,,Ak){\cal P}=(A_1,\ldots,A_k) be a monotone partition of V(G)V(G) into cliques. The box graph b(G;P)b(G;{\cal P}) has a chordless cycle Ai1AicAi1A_{i_1}\dots A_{i_c}A_{i_1} for which the induced subgraph on the corresponding parts has bounded clique-width. The bounded-cycle clique-width conjecture. There exists a function ff such that, if for every chordless cycle Ai1AicAi1A_{i_1}\dots A_{i_c}A_{i_1} of b(G;P)b(G;{\cal P}) one has

cwd(G[Ai1Aic])x,\operatorname{cwd}(G[A_{i_1}\cup\dots\cup A_{i_c}])\leq x,

then

cwd(G)f(k,x).\operatorname{cwd}(G)\leq f(k,x).

This would extend the forest case, where the clique-width is bounded by k+1k+1, to monotone partitions whose box graphs may contain cycles. The supplied text gives no resolution, so the conjecture remains open.

Sources & referencesView supporting material

Primary source

Chính T. Hoàng, Ramin Javadi and Nicolas Trotignon, “On the structure of (4K_1, C_4, P_6)-free graphs”, arXiv:2511.23195 (2025).

Additional references

2 papers in this index state this conjecture (2021–2025). The statement above is taken from the most recent of them; the others are arXiv:2102.09994.

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.