Tag Info

17

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

8

One example is the vertex disjoint paths problem, which is linear time solvable in graphs of bounded tree width but NPC in graphs of clique width at most $6$.

5

After a while I found an answer in the literature, so I'm posting it here in case it is useful to someone else. It is in fact possible to re-balance clique-width expressions so that they have logarithmic depth. The result is given in the paper "Graph operations characterizing rank-width and balanced graph expressions" by Courcelle and Kanté, WG '08. I quote ...

2

Cographs have clique width 2, and the number of cographs of size $n$ is asymptotically equal to $3.56^n$. See https://mathoverflow.net/questions/37875/bound-on-the-number-of-unlabeled-cographs-on-n-vertices. I am not sure how many graphs with a given clique-width $k$ exist.

1

I will try to answer this old question of yours, although I am not sure my answer is conclusive but it should point you in the right direction. First let us discuss linear clique-width. If a graph has linear clique-width $k$, and one add $1$ vertex to the graph, that vertex can always be placed first in the ordering with a unique color. Hence linear clique-...

Only top voted, non community-wiki answers of a minimum length are eligible