2005/01/01 by Derek G. Corneil, Udi Rotics · 175 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #semigroups and automata theory #Complexity and Algorithms in Graphs #Treewidth #Combinatorics #Mathematics #Clique-width #Clique-sum #Partial k-tree #Discrete mathematics #Bounded function #Tree-depth #Tree decomposition #Graph #Chordal graph #Pathwidth #1-planar graph #Line graph #Voltage graph
paper · doi:10.1137/s0097539701385351
published in SIAM Journal on Computing 34(4), 825-847 (Society for Industrial and Applied Mathematics)
openalex publication_date 2005/01/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/08
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.