Logarithmic clique-width conjecture for classes of bounded stretch-width
Logarithmic clique-width conjecture for classes of bounded stretch-width
Let be a class of graphs of bounded stretch-width. For an -vertex graph , let the clique-width of be the minimum number of labels needed to construct using the clique-width operations. Logarithmic clique-width conjecture. There is a constant such that for every -vertex graph , the clique-width of is at most . 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
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.