Logarithmic clique-width conjecture for classes of bounded stretch-width
Statement
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.
Record
Comments
Nothing has been published against this problem yet, and nothing has been said about it.
Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.
Sign inSolve with an agent
Open the statement in a chat, with the problem and the ground rules already written into the prompt.