BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Discrete Mathematics Group - ECPv6.15.20//NONSGML v1.0//EN
CALSCALE:GREGORIAN
METHOD:PUBLISH
X-WR-CALNAME:Discrete Mathematics Group
X-ORIGINAL-URL:https://dimag.ibs.re.kr
X-WR-CALDESC:Events for Discrete Mathematics Group
REFRESH-INTERVAL;VALUE=DURATION:PT1H
X-Robots-Tag:noindex
X-PUBLISHED-TTL:PT1H
BEGIN:VTIMEZONE
TZID:Asia/Seoul
BEGIN:STANDARD
TZOFFSETFROM:+0900
TZOFFSETTO:+0900
TZNAME:KST
DTSTART:20200101T000000
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20210511T163000
DTEND;TZID=Asia/Seoul:20210511T173000
DTSTAMP:20260419T044821
CREATED:20210420T015716Z
LAST-MODIFIED:20240705T185043Z
UID:3969-1620750600-1620754200@dimag.ibs.re.kr
SUMMARY:Mark Siggers\, The list switch homomorphism problem for signed graphs
DESCRIPTION:A signed graph is a graph in which each edge has a positive or negative sign. Calling two graphs switch equivalent if one can get from one to the other by the iteration of the local action of switching all signs on edges incident to a given vertex\, we say that there is a switch homomorphism from a signed graph $G$ to a signed graph $H$ if there is a sign preserving homomorphism from $G’$ to $H$ for some graph $G’$ that is switch equivalent to $G$.  By reductions to CSP this problem\, and its list version\, are known to be either polynomial time solvable or NP-complete\, depending on $H$.  Recently those signed graphs $H$ for which the switch homomorphism problem is in $P$ were characterised.  Such a characterisation is yet unknown for the list version of the problem. \nWe talk about recent work towards such a characterisation and about how these problems fit in with bigger questions that still remain around the recent CSP dichotomy theorem.
URL:https://dimag.ibs.re.kr/event/2021-05-11/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
END:VCALENDAR