<p>This recent <a href="http://arxiv.org/abs/1306.6168">paper</a> finally proves that edge contractions do not preserve the property that a set of graphs has bounded 
clique-width.</p>

CC BY-SA 3.0
2013-07-10T23:38:03.630Z
2013-07-10T23:38:03.630Z
user13136
<p>This may be a pre-answer:
in <a href="http://arxiv.org/abs/cs/0701185">this 2007 arXiv paper</a> (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) &lt; cw(G^{x,y})$, where $G^{x,y}$ is the graph $G$ with edge $\{x,y\}$ contracted.</p>

CC BY-SA 2.5
2010-12-22T18:37:41.133Z
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 :)
Martin Lackner
CC BY-SA 2.5
2010-12-23T10:53:46.980Z
Isn’t that problem the opposite direction from what is being asked here?
Tsuyoshi Ito
CC BY-SA 2.5
2010-12-23T17:31:04.043Z
Only in the sense that this question asks for a counterexample.
Martin Lackner
CC BY-SA 2.5
2010-12-22T16:54:48.493Z
2010-12-22T16:54:48.493Z
Mathieu Chapelle
<p>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?</p>

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

<graph-theory><co.combinatorics><cliquewidth>
Is clique-width preserved under edge contractions?
Martin Lackner
# Is clique-width preserved under edge contractions?

(Asked by: username_0 on 2010-12-22)

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.

**Tags:** graph-theory, co.combinatorics, cliquewidth

---

## 2 answers

### Answer by username_2 on 2010-12-22. Score: 16 | Accepted answer

This may be a pre-answer:
in [this 2007 arXiv paper](http://arxiv.org/abs/cs/0701185) (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.

> **Comments:**
> **username_0**: 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 :)  
> **username_3**: Isn’t that problem the opposite direction from what is being asked here?  
> **username_0**: Only in the sense that this question asks for a counterexample.  

---

### Answer by username_1 on 2013-07-10. Score: 17

This recent [paper](http://arxiv.org/abs/1306.6168) finally proves that edge contractions do not preserve the property that a set of graphs has bounded
clique-width.


---

