Bounded clique-width from bounded chordless-cycle subgraphs

About 5 years old · traced to

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 Ai1…AicAi1A_{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 Ai1…AicAi1A_{i_1}\dots A_{i_c}A_{i_1} of b(G;P)b(G;{\cal P}) one has

cwd⁡(G[Ai1∪⋯∪Aic])≤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.

References

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.