Logarithmic clique-width conjecture for classes of bounded stretch-width

Let C\mathcal C be a class of graphs of bounded stretch-width. For an nn-vertex graph GCG\in\mathcal C, let the clique-width of GG be the minimum number of labels needed to construct GG using the clique-width operations. Logarithmic clique-width conjecture. There is a constant cc such that for every nn-vertex graph GCG\in\mathcal C, the clique-width of GG is at most clognc\log n. This would clarify whether bounded stretch-width generally implies essentially logarithmic clique-width; the paper provides a separating example with essentially logarithmic clique-width, but the general statement is posed as an open question.

Sources & referencesView supporting material

Primary source

Édouard Bonnet and Julien Duron, “Stretch-width”, arXiv:2305.12023 (2023).

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.