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:20210817T163000
DTEND;TZID=Asia/Seoul:20210817T173000
DTSTAMP:20260424T113001
CREATED:20210817T073000Z
LAST-MODIFIED:20240707T081153Z
UID:4242-1629217800-1629221400@dimag.ibs.re.kr
SUMMARY:Linda Cook\, Two results on graphs with holes of restricted lengths
DESCRIPTION:We call an induced cycle of length at least four a hole. The parity of a hole is the parity of its length. Forbidding holes of certain types in a graph has deep structural implications. In 2006\, Chudnovksy\, Seymour\, Robertson\, and Thomas famously proved that a graph is perfect if and only if it does not contain an odd hole or a complement of an odd hole. In 2002\, Conforti\, Cornuéjols\, Kapoor\, and Vuškovíc provided a structural description of the class of even-hole-free graphs. I will describe the structure of all graphs that contain only holes of length $\ell$ for every $\ell \geq 7$ (joint work with Jake Horsfield\, Myriam Preissmann\, Paul Seymour\, Ni Luh Dewi Sintiari\, Cléophée Robin\, Nicolas Trotignon\, and Kristina Vuškovíc. \nAnalysis of how holes interact with graph structure has yielded detection algorithms for holes of various lengths and parities. In 1991\, Bienstock showed it is NP-Hard to test whether a graph G has an even (or odd) hole containing a specified vertex $v \in V(G)$. In 2002\, Conforti\, Cornuéjols\, Kapoor\, and Vuškovíc gave a polynomial-time algorithm to recognize even-hole-free graphs using their structure theorem. In 2003\, Chudnovsky\, Kawarabayashi\, and Seymour provided a simpler and slightly faster algorithm to test whether a graph contains an even hole. In 2019\, Chudnovsky\, Scott\, Seymour\, and Spirkl provided a polynomial-time algorithm to test whether a graph contains an odd hole. Later that year\, Chudnovsky\, Scott\, and Seymour strengthened this result by providing a polynomial-time algorithm to test whether a graph contains an odd hole of length at least $\ell$ for any fixed integer $\ell \geq 5$. I will present a polynomial-time algorithm (joint work with Paul Seymour) to test whether a graph contains an even hole of length at least $\ell$ for any fixed integer $\ell \geq 4$.
URL:https://dimag.ibs.re.kr/event/2021-08-17/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
END:VCALENDAR