Noleen Köhler, Twin-Width VIII: Delineation and Win-Wins
Room B332 IBS (기초과학연구원)We introduce the notion of delineation. A graph class
10 events found.
Seminars and Colloquiums
Pedro Montealegre, A Meta-Theorem for Distributed Certification
Zoom ID: 869 4632 6610 (ibsdimag)Distributed certification, whether it be proof-labeling schemes, locally checkable proofs, etc., deals with the issue of certifying the legality of a distributed system with respect to a given boolean predicate. A certificate …
Jan Hladký, Invitation to graphons
Zoom ID: 224 221 2686 (ibsecopro)The first course in graph theory usually covers concepts such as matchings, independent sets, colourings, and forbidden subgraphs. Around 2004, Borgs, Chayes, Lovász, Sós, Szegedy, and Vestergombi introduced a very …
Abhishek Methuku, A proof of the Erdős–Faber–Lovász conjecture
Room B332 IBS (기초과학연구원)The Erdős–Faber–Lovász conjecture (posed in 1972) states that the chromatic index of any linear hypergraph on n vertices is at most n. In this talk, I will sketch a proof …
Benjamin Bergougnoux, Tight Lower Bounds for Problems Parameterized by Rank-width
Zoom ID: 869 4632 6610 (ibsdimag)We show that there is no
Raphael Steiner, Strengthening Hadwiger’s conjecture for 4- and 5-chromatic graphs
Room B332 IBS (기초과학연구원)Hadwiger's famous coloring conjecture states that every t-chromatic graph contains a
Robert Hickingbotham, Treewidth, Circle Graphs and Circular Drawings
Zoom ID: 869 4632 6610 (ibsdimag)A circle graph is an intersection graph of a set of chords of a circle. In this talk, I will describe the unavoidable induced subgraphs of circle graphs with large …
Meike Hatzel, Fixed-Parameter Tractability of Directed Multicut with Three Terminal Pairs Parametrised by the Size of the Cutset: Twin-Width Meets Flow-Augmentation
Room B332 IBS (기초과학연구원)We show fixed-parameter tractability of the Directed Multicut problem with three terminal pairs (with a randomized algorithm). This problem, given a directed graph
Daniel Altman, On an arithmetic Sidorenko conjecture, and a question of Alon
Zoom ID: 224 221 2686 (ibsecopro)Let
Maya Sankar, The Turán Numbers of Homeomorphs
Room B332 IBS (기초과학연구원)Let