기초과학VOD

BASIC SCI VOD

  •   >  
  • 연구동향
  •   >  
  • 기초과학VOD
Super Title 2017 Discrete Math 세미나
Title The Complexity of Counting Generalized Colorings: New Results and Challenges
Speaker Johann A. Makowsky ( Faculty of Computer Science, Technion – Israel Ins ) Date 2017-07-14
Host KAIST Place KAIST
VOD
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

이 페이지에서 제공하는 정보에 만족하십니까?

  • 수리과학연구정보센터
  • 환경지질연구정보센터
  • 해양수산연구정보센터
  • 자연과학분야
  • 한국연구제단