Cookie Setting MathNet Korea

이전페이지 이동
The reconfiguration problem for graph homomorpisms
[2018 Discrete Math 세미나]
Date: 2018-04-03
Speaker : Mark Siggers (Kyungpook National University)
Abstract : For problems with a discrete set of solutions, a reconfiguration problem defines solutions to be adjacent if they meet some condition of closeness, and then asks for two given solutions it there is a path between them in the set of all solutions. The reconfiguration problem for graph homomorphisms has seen fair activity in recent years. Fixing a template, the problem Recol(H) for a graph H asks if one can get from one H-colouring of a graph G to another by changing one vertex at a time, always remaining an H-colouring. If the changed vertex has a loop, it must move to an adjecent vertex Depending on H, the problem seems to be either polynomial time solvable or PSPACE-complete. We discuss many recent results in the area and work towards conjecturing for which H the problem is PSPACE-complete. This is joint work with Rick Brewster, Jae-baek Lee, Ben Moore and Jon Noel.
Information Center for Mathematical Sciences KAIST
34141 대전광역시 유성구 대학로 291 (구성동373-1)
한국과학기술원(KAIST) 수리과학정보센터
전화 042-350-8196
e-mail :
Copyright (C) 2018. ICMS All Rights Reserved.