Bounded clique-width from bounded chordless-cycle subgraphs
Bounded clique-width from bounded chordless-cycle subgraphs
Let be a graph, and let be a monotone partition of into cliques. The box graph has a chordless cycle for which the induced subgraph on the corresponding parts has bounded clique-width. The bounded-cycle clique-width conjecture. There exists a function such that, if for every chordless cycle of one has
then
This would extend the forest case, where the clique-width is bounded by , 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
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.