Title    name
2017 Discrete Math 세미나
  Speaker Johann A. Makowsky
  Date 2017-07-14
  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