Youngho Yoo (유영호), Approximating TSP walks in subcubic graphs

Room B332 IBS (기초과학연구원)

The Graphic Travelling Salesman Problem is the problem of finding a spanning closed walk (a TSP walk) of minimum length in a given connected graph. The special case of the Graphic TSP on subcubic graphs has been studied extensively due to their worst-case behaviour in the famous $\frac{4}{3}$-integrality-gap conjecture on the "subtour elimination" linear programming

Mamadou Moustapha Kanté, MSOL-Definable decompositions

Room B332 IBS (기초과학연구원)

I will first introduce the notion of recognisability of languages of terms and then its extensions to sets of relational structures. In a second step, I will discuss relations with decompositions of graphs/matroids and why their MSOL-definability is related to understanding recognisable sets. I will finally explain  how to define in MSOL branch-decompositions for finitely

Noleen Köhler, Twin-Width VIII: Delineation and Win-Wins

Room B332 IBS (기초과학연구원)

We introduce the notion of delineation. A graph class $\mathcal C$ is said delineated by twin-width (or simply, delineated) if for every hereditary closure $\mathcal D$ of a subclass of $\mathcal C$, it holds that $\mathcal D$ has bounded twin-width if and only if $\mathcal D$ is monadically dependent. An effective strengthening of delineation for

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 $2^{o(k^2)} n^{O(1)}$ time algorithm for Independent Set on $n$-vertex graphs with rank-width $k$, unless the Exponential Time Hypothesis (ETH) fails. Our lower bound matches the $2^{O(k^2)} n^{O(1)}$ time algorithm given by Bui-Xuan, Telle, and Vatshelle and it answers the open question of Bergougnoux and Kanté . We also show

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 $K_t$-minor. Holroyd conjectured the following strengthening of Hadwiger's conjecture: If G is a t-chromatic graph and S⊆V(G) takes all colors in every t-coloring of G, then G contains a $K_t$-minor rooted at S. We prove this conjecture in the first open case of t=4.

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 $G$, pairs of vertices (called terminals) $(s_1,t_1)$, $(s_2,t_2)$, and $(s_3,t_3)$, and an integer $k$, asks to find a set of at most $k$ non-terminal vertices in $G$ that intersect all $s_1t_1$-paths, all

IBS 이산수학그룹 Discrete Mathematics Group
기초과학연구원 수리및계산과학연구단 이산수학그룹
대전 유성구 엑스포로 55 (우) 34126
IBS Discrete Mathematics Group (DIMAG)
Institute for Basic Science (IBS)
55 Expo-ro Yuseong-gu Daejeon 34126 South Korea
E-mail: dimag@ibs.re.kr, Fax: +82-42-878-9209
Copyright © IBS 2018. All rights reserved.