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$

2 Answers 2

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

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