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:20210101T000000
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20220707T100000
DTEND;TZID=Asia/Seoul:20220707T110000
DTSTAMP:20260419T093735
CREATED:20220707T010000Z
LAST-MODIFIED:20240707T075642Z
UID:5783-1657188000-1657191600@dimag.ibs.re.kr
SUMMARY:Sepehr Hajebi\, Holes\, hubs and bounded treewidth
DESCRIPTION:A hole in a graph $G$ is an induced cycle of length at least four\, and for every hole $H$ in $G$\, a vertex $h\in G\setminus H$ is called a $t$-hub for $H$ if $h$ has at least $t$ neighbor in $H$. Sintiari and Trotignon were the first to construct graphs with arbitrarily large treewidth and no induced subgraph isomorphic to the “basic obstructions\,” that is\, a fixed complete graph\, a fixed complete bipartite graph (with parts of equal size)\, all subdivisions of a fixed wall and line graphs of all subdivisions of a fixed wall. They named their counterexamples “layered wheels” for a good reason: layered wheels contain wheels in abundance\, where a wheel means a hole with a $3$-hub. In accordance\, one may ask whether graphs with no wheel and no induced subgraph isomorphic to the basic obstructions have bounded treewidth. This was also disproved by a recent construction due to Davies. But holes with a $2$-hub cannot be avoided in graphs with large treewidth: graphs containing no hole with a $2$-hub and no induced subgraph isomorphic to the basic obstructions have bounded treewidth. I will present a proof of this result\, and will also give an overview of related works.\nBased on joint work with Tara Abrishami\, Bogdan Alecu\, Maria Chudnovsky\, Sophie Spirkl and Kristina Vušković.
URL:https://dimag.ibs.re.kr/event/2022-07-07/
LOCATION:Zoom ID: 869 4632 6610 (ibsdimag)
CATEGORIES:Virtual Discrete Math Colloquium
END:VEVENT
END:VCALENDAR