Group for Research in Decision Analysis

On the Clique-Width of Graphs

Vadim Lozin

The notion of clique-width is of primary importance in algorithmic graph theory, since many problems being NP-hard in general graphs become polynomial-time solvable when restricted to graphs of bounded clique-width. In this talk we address the question of deciding whether the clique-width of graphs in a certain class is bounded or not. We first present several general results that might be helpful in answering the question, and then apply those results to variety of graph classes.

Different parts of this work have been done in collaboration with R. Boliac (Rutgers University), A. Brandstadt (Rostock University, Germany), D. Rautenbach (Bonn University, Germany).