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.

$\endgroup$
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.

$\endgroup$
  • $\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 Dec 22 '10 at 18:37
  • $\begingroup$ Isn’t that problem the opposite direction from what is being asked here? $\endgroup$ – Tsuyoshi Ito Dec 23 '10 at 10:53
  • $\begingroup$ Only in the sense that this question asks for a counterexample. $\endgroup$ – Martin Lackner Dec 23 '10 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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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