Clique-width is a graph parameter that measures in a certain sense the complexity of a graph. It is known that MSO_1 queries can be evaluated in polynomial time on classes of graphs with effectively bounded clique-width. Here MSO_1 denotes the fragment of Monadic Second Order Logic with second-order quantification on vertex sets. NP-hard problems like 3-colorability can be expressed as MSO_1 queries.
This talk will survey the concept of clique-width, its advantages and its limits. In particular, new NP-hardness results for the recognition of graphs with bounded clique-width will be presented; these results were recently obtained in joint work with M.R. Fellows, F. Rosamond, and U. Rotics.