On the Relationship Between Clique-Width and Treewidth

Abstract

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 * 2k - 1 + 1. In this paper, we improve this result by showing that the clique-width of G is at most 3 * 2k - 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^{\lfloor k/2\rfloor - 1}$.