Cookie Setting MathNet Korea

이전페이지 이동
The Complexity of Counting Generalized Colorings: New Results and Challenges
[2017 Discrete Math 세미나]
Date: 2017-07-14
Speaker : Johann A. Makowsky (Faculty of Computer Science, Technion – Israel Ins)
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
Information Center for Mathematical Sciences KAIST
34141 대전광역시 유성구 대학로 291 (구성동373-1)
한국과학기술원(KAIST) 수리과학정보센터
전화 042-350-8196
e-mail :
Copyright (C) 2018. ICMS All Rights Reserved.