Ilkyoo Choi (최일규), Flexibility of Planar Graphs

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

Oftentimes in chromatic graph theory, precoloring techniques are utilized in order to obtain the desired coloring result. For example, Thomassen's proof for 5-choosability of planar graphs actually shows that two adjacent vertices on the same face can be precolored. In this vein, we investigate a precoloring extension problem formalized by Dvorak, Norin, and Postle named flexibility. Given a

Paloma T. Lima, Graph Square Roots of Small Distance from Degree One Graphs


Given a graph class $\mathcal{H}$, the task of the $\mathcal{H}$-Square Root problem is to decide whether an input graph G has a square root H that belongs to $\mathcal{H}$. We are interested in the parameterized complexity of the problem for classes $\mathcal{H}$ that are composed by the graphs at vertex deletion distance at most $k$

Akansha Agrawal, Polynomial Kernel for Interval Vertex Deletion


Given a graph G and an integer k, the Interval Vertex Deletion (IVD) problem asks whether there exists a vertex subset S of size at most k, such that G-S is an interval graph. A polynomial kernel for a parameterized problem is a polynomial time preprocessing algorithm that outputs an equivalent instance of the problem whose size is bounded by

Robert Ganian, Solving Integer Linear Programs by Exploiting Variable-Constraint Interactions


Integer Linear Programming (ILP) is among the most successful and general paradigms for solving computationally intractable optimization problems in computer science. ILP is NP-complete, and until recently we have lacked a systematic study of the complexity of ILP through the lens of variable-constraint interactions. This changed drastically in recent years thanks to a series of results that together lay out a


Nonlinear Algebra in Daejeon (Postponed)

IBS Science Culture Center

Program Summer School @ KAIST (August 4-7, 2020) Discussion Weekend (August 8-9, 2020) Workshop @ IBS Science Culture Center (August 10-13, 2020) Website: Organizing Committee Insong Choe (Konkuk U.) Kangjin Han (DGIST) David Hyeon (SNU) Sijong Kwak (KAIST) Yongnam Lee (KAIST) Anton Leykin (Georgia Tech) Sang-il Oum (IBS & KAIST) Frank Sottile (TAMU)

Gwenaël Joret, Packing and covering balls in graphs excluding a minor


In 2007, Chepoi, Estellon, and Vaxès conjectured that there exists a universal constant $c>0$ such that the following holds for every positive integers $r$ and $k$, and every planar graph $G$: Either $G$ contains $k$ vertex-disjoint balls of radius $r$, or there is a subset of vertices of size at most $c k$ meeting all


2020 IBS Workshop on Extremal and Probabilistic Combinatorics (postponed)

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

Date August 24, 2020 - August 28, 2020 Arrival: August 23 Sunday. Departure: August 29, Saturday Venue Institute for Basic Science,  55 Expo-ro, Yuseong-gu, Daejeon, South Korea Invited Speakers Julia Böttcher, London School of Economics Boris Bukh, Carnegie Mellon University Amin Coja-Oghlan, Goethe University David Conlon, Caltech Penny Haxell, University of Waterloo Hao Huang, Emory University Jeff Kahn, Rutgers University