Title    name
2017 Discrete Math 세미나
 
  Title
  Speaker Johann A. Makowsky
  Date 2017-07-14
  Host
  Place KAIST
  File  의 1 번째 Real Media 동영상입니다.   
 
Abstract : Let P be a graph property. We look at graph colorings with k colors where each color class induces a graph satisfying P. By a result of Makowsky and Zilber (2005) the number of such colorings xP(G;k) is a polynomial in k. We present recent results and open problems on the complexity of evaluating xP(G;L) for various properties P and (not only integer) values of L. This is joint work with A. Goodall, M. Hermann, T. Kotek and S. Noble which was initiated during last year’s program “Counting Complexity and Phase Transitions”. See also https://arxiv.org/abs/1701.06639