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.
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 is assigned to each process in the system by a non-trustable oracle, and the processes are in charge of verifying these certificates, so that two …
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 fruitful limit perspective on graphs. The central objects of this theory, so-called graphons, are suitable measurable counterparts to graphs. In the talk, I will outline …
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 of this conjecture for every large n. Joint work with D. Kang, T. Kelly, D. Kühn and D. Osthus.
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 treewidth. This includes examples that are far from the `usual suspects'. Our results imply that treewidth and Hadwiger number are linearly tied on the class …
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