I found this article


* J. A. Makowsky and U. Rotics, *On the clique-width of graphs with few $P\_4$s*, International Journal of Foundations of Computer Science Vol. 10, No. 03 (1999) pp. 329-348, doi:[10.1142/S0129054199000241](https://doi.org/10.1142/S0129054199000241),
[ResearchGate](https://www.researchgate.net/publication/220180873_On_the_Clique-Width_of_Graphs_with_Few_P).


On page 7 it has a demonstration for $C\_n$ clique-width upper bound, but it doesn't mention the idea to show the equality $\operatorname{cw}(C\_n) = 4$. Does anyone have any ideas?



Clique width of C_n
The upper bound in Makowsky and Rotics says that with 4 labels, you can build $P\_{n-1}$ in such a way that the two leaves have unique labels. From there you make all the non-leaves the same label, leaving you with an unused label. Then you insert a new vertex with this unused label and make it adjacent to the two leaves of your $P\_{n-1}$ to get $C\_n$. This actually shows that the *linear* clique-width of $C\_n$ is at most $4$, and it also shows that the challenge isn't building $C\_n$, but building $P\_{n-1}$ with that labeling.


I believe the following works for a lower bound. Consider a construction of $C\_n$ that uses four (or fewer) labels. Look at the last step of this construction that consists of taking a union. You can argue that you must be adding a single vertex to $P\_{n-1}$ at that step, because there are not enough labels to do anything else. Therefore after you insert this final vertex, the two leaves of the $P\_{n-1}$ must have different labels from every other vertex of the $P\_{n-1}$, because you are going to make your new vertex adjacent to these and only these vertices. (This is a weaker labeling than what Makowsky and Rotics use in their upper bound; the labeling they used is nicer to establish by induction, but we'll show below that this weaker labeling is just as difficult to build.)


As we observed above, building $P\_{n-1}$ with such a labeling is the real challenge, so now you have to consider how that can be built. Again consider the last step that consists of taking a union. Again, you can argue that you must be adding a single vertex to $P\_{n-2}$ at that step, because again there are not enough labels to do anything else. It is *this* vertex that needs the fourth label. That is because the two leaves of your $P\_{n-2}$ must have unique labels (this new vertex will be adjacent to only one of them, but the final vertex will be adjacent to both of them and nothing else), and the interior vertices of the $P\_{n-2}$ must use a third label.


