Logarithmic clique-width for cyclic box graphs

Let GG be a graph and let P{\cal P} be a monotone partition of V(G)V(G) into cliques. Assume that the box graph b(G;P)b(G;{\cal P}) is a chordless cycle. The logarithmic cyclic-box conjecture. There exists a function gg such that

cwd(G)g(k)logV(G).\operatorname{cwd}(G)\leq g(k)\log |V(G)|.

The preceding forest result shows a constant clique-width bound when the box graph is acyclic, while this conjecture predicts a logarithmic bound when it is a single chordless cycle. 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).

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.