BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Discrete Mathematics Group - ECPv6.15.20//NONSGML v1.0//EN
CALSCALE:GREGORIAN
METHOD:PUBLISH
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:20210728T150000
DTEND;TZID=Asia/Seoul:20210728T160000
DTSTAMP:20260420T061101
CREATED:20210607T135955Z
LAST-MODIFIED:20240705T184022Z
UID:4228-1627484400-1627488000@dimag.ibs.re.kr
SUMMARY:Maria Chudnovsky\, Induced subgraphs and tree decompositions
DESCRIPTION:Tree decompositions are a powerful tool in structural graph theory; they are traditionally used in the context of forbidden graph minors. Connecting tree decompositions and forbidden induced subgraphs has until recently remained out of reach. \nTree decompositions are closely related to the existence of  “laminar collections of separations” in a graph\, which roughly means that the separations in the collection “cooperate” with each other\, and the pieces that are obtained when the graph is simultaneously decomposed by all the separations in the collection “line up” to form a tree structure. Such collections of separations come up naturally in the context of forbidden minors. \nIn the case of families where induced subgraphs are excluded\, while there are often natural separations\, they are  usually very far from forming a laminar collection. In what follows we mostly focus on families of graphs of bounded degree. It turns out that due to the bound on the degree\, these collections of natural separations can be partitioned into a bounded number of laminar collections. This in turn allows to us obtain a wide variety of structural and algorithmic results\, which we will survey in this talk.
URL:https://dimag.ibs.re.kr/event/2021-07-28/
LOCATION:Zoom ID: 869 4632 6610 (ibsdimag)
CATEGORIES:Virtual Discrete Math Colloquium
END:VEVENT
END:VCALENDAR