skip to content

On the clique-width of graphs

Presented by: 
S Szeider [Durham]
Thursday 2nd March 2006 - 15:30 to 16:15
INI Seminar Room 1

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.

    University of Cambridge Research Councils UK
        Clay Mathematics Institute London Mathematical Society NM Rothschild and Sons