KAIST Discrete Math Seminar

The clique-width parameter provides a rough measure of the complexity of structure in (classes of) graphs. A well-known result of Courcelle, Makowsky and Rotics shows that many problems on graphs which are NP-hard in general can be solved in polynomial time in any class of graphs of bounded clique-width. Unlike the better-known treewidth graph parameter, clique-width respects the induced subgraph ordering, and in particular it can handle dense graphs. However, also unlike treewidth there is no known characterisation of the minimal classes of graphs which have unbounded clique-width.
In this talk, I will survey a number of results and techniques for studying the interface between bounded and unbounded clique-width. Of particular interest are insights from the combinatorial study of permutations (“permutation patterns”), which has brought to light several more minimal graph classes with unbounded clique-width, and also suggests that a restricted version of the parameter, called linear clique-width, often appears to characterise the interface. Time-permitting, I will also discuss recent developments and open problems in the relationship between clique-width and well-quasi-ordering.