On the relationship between clique-width and treewidth
Treewidth is generally regarded as one of the most useful parameterizations of a graph's construction. Clique-width is a similar parameterization that shares one of the powerful properties of treewidth, namely: if a graph is of bounded treewidth ( or clique-width), then there is a polynomial time algorithm for any graph problem expressible in monadic second order logic, using quantifiers on vertices ( in the case of clique-width you must assume a clique-width parse expression is given). In studying the relationship between treewidth and clique-width, Courcelle and Olariu [ Discrete Appl. Math., 101 ( 2000), pp. 77 - 114] showed that any graph of bounded treewidth is also of bounded clique-width; in particular, for any graph G with treewidth k, the clique-width of G is at most 4 * 2(k-1) + 1. In this paper, we improve this result by showing that the clique-width of G is at most 3 * 2(k-1) and, more importantly, that there is an exponential lower bound on this relationship. In particular, for any k, there is a graph G with treewidth equal to k, where the clique-width of G is at least 2([k/2])- 1.
clique-width treewidth