Title    name
2015 Discrete Math 세미나
 
  Title
  Speaker Robert Brignall
  Date 2015-11-11
  Host
  Place KAIST
  File  의 1 번째 Real Media 동영상입니다.   
 
Abstract : 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 (“p rmutation 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.