◈ 학술지
◈ 도서
◈ 전자학술지
◈ 투고요령
◈ 수학신간도서
◈ MSC
◈ 논문검색
◈ 학술행사
홈 > 학술정보 >학술행사 > 세미나
KAIST 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 16:00:00
Host
KAIST
Place
E6-1 Room 1409
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
개인정보보호정책 l 이메일주소집단수집금지 l 뷰어다운로드
qr코드