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:20240101T000000
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20250422T163000
DTEND;TZID=Asia/Seoul:20250422T173000
DTSTAMP:20260417T052446
CREATED:20250210T062933Z
LAST-MODIFIED:20250414T092141Z
UID:10558-1745339400-1745343000@dimag.ibs.re.kr
SUMMARY:Marcin Briański\, Burling Graphs as (almost) universal obstacles to  $\chi$-boundedness
DESCRIPTION:What causes a graph to have high chromatic number? One obvious reason is containing a large clique (a set of pairwise adjacent vertices). This naturally leads to investigation of \(\chi\)-bounded classes of graphs — classes where a large clique is essentially the only reason for large chromatic number. \nUnfortunately\, many interesting graph classes are not \(\chi\)-bounded. An eerily common obstruction to being \(\chi\)-bounded are the Burling graphs — a family of triangle-free graphs with unbounded chromatic number. These graphs have served as counterexamples in many settings: demonstrating that graphs excluding an induced subdivision of \(K_{5}\) are not \(\chi\)-bounded\, that string graphs are not \(\chi\)-bounded\, that intersection graphs of boxes in \({\mathbb{R}}^{3}\) are not \(\chi\)-bounded\, and many others. \nIn many of these cases\, this sequence is the only known obstruction to \(\chi\)-boundedness. This led Chudnovsky\, Scott\, and Seymour to conjecture that any graph of sufficiently high chromatic number must either contain a large clique\, an induced proper subdivision of a clique\, or a large Burling graph as an induced subgraph. \nThe prevailing belief was that this conjecture should be false. Somewhat surprisingly\, we did manage to prove it under an extra assumption on the “locality” of the chromatic number — that the input graph belongs to a \(2\)-controlled family of graphs\, where a high chromatic number is always certified by a ball of radius \(2\) with large chromatic number. \nIn this talk\, I will present this result and discuss its implications in structural graph theory\, and algorithmic implications to colouring problems in specific graph families. \nThis talk is based on joint work with Tara Abrishami\, James Davies\, Xiying Du\, Jana Masaříková\, Paweł Rzążewski\, and Bartosz Walczak conducted during the STWOR2 workshop in Chęciny Poland.
URL:https://dimag.ibs.re.kr/event/2025-04-22/
LOCATION:Room B332\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
END:VCALENDAR