13
$\begingroup$

Let $G$ be class of graphs with bounded clique-width. In each graph in $G$ some edges are contracted (e.g. randomly). Is now the clique-width still bounded?

In case it is (in general) no longer bounded, I would be very interested in a counter-example.

Improve this question
$\endgroup$

2 Answers 2

Reset to default
16
$\begingroup$

This may be a pre-answer: in this 2007 arXiv paper (Problem 4.9), it is stated as an open problem whether one can find a graph $G$ and an edge $\{x,y\} \in E(G)$ such that $cw(G) < cw(G^{x,y})$, where $G^{x,y}$ is the graph $G$ with edge $\{x,y\}$ contracted.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Thanks a lot for your answer! That is a valuable reference for me. In case no one has solved it in the meantime, my question is more or less answered :) $\endgroup$
    – Martin Lackner
    Commented Dec 22, 2010 at 18:37
  • $\begingroup$ Isn’t that problem the opposite direction from what is being asked here? $\endgroup$
    – Tsuyoshi Ito
    Commented Dec 23, 2010 at 10:53
  • $\begingroup$ Only in the sense that this question asks for a counterexample. $\endgroup$
    – Martin Lackner
    Commented Dec 23, 2010 at 17:31
17
$\begingroup$

This recent paper finally proves that edge contractions do not preserve the property that a set of graphs has bounded clique-width.

Improve this answer
$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.