2021 Combinatorics Workshop (2021 조합론 학술대회)

Towards a dichotomy classification for list switch homomorphism problem for signed graphs

20 Dec 2021, 18:00

25m

Yangpyeong The Bloomvista

Contributed talk Session

Speaker

Hyobin Kim (Kyungpook National University)

Description

The list switch homomorphisms problem $LSwHom(H)$ is for a signed graph $G$ with list if there is a switch homomorphism to $H$ preserving lists. We present towards a structural characterisation of the signed graphs $H$ for which the $LSwHom(H)$ problem is polynomial time solvable. We prove the characterisation in the case that the signed graph is reflexive.