Akanksha 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. …
10 events found.
Virtual Discrete Math Colloquium
Events
-
-
Zoom ID: 869 4632 6610 (ibsdimag)
-
-
Robert Ganian, Solving Integer Linear Programs by Exploiting Variable-Constraint Interactions
Zoom ID: 869 4632 6610 (ibsdimag)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 …
-
Gwenaël Joret, Packing and covering balls in graphs excluding a minor
Zoom ID: 869 4632 6610 (ibsdimag)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 …
-
Nick Brettell, On the graph width parameter mim-width
Zoom ID: 869 4632 6610 (ibsdimag)Maximum induced matching width, also known as mim-width, is a width parameter for graphs introduced by Vatshelle in 2012. This parameter can be defined over branch decompositions of a graph …
-
-
Sebastian Siebertz, Rank-width meets stability
Zoom ID: 869 4632 6610 (ibsdimag)Forbidden graph characterizations provide a convenient way of specifying graph classes, which often exhibit a rich combinatorial and algorithmic theory. A prime example in graph theory are classes of bounded …
-
Luke Postle, Further progress towards Hadwiger’s conjecture
Zoom ID: 869 4632 6610 (ibsdimag)In 1943, Hadwiger conjectured that every graph with no $K_t$ minor is $(t-1)$-colorable for every $t\ge 1$. In the 1980s, Kostochka and Thomason independently proved that every graph with no $K_t$ …
-
Zihan Tan, Towards Tight(er) Bounds for the Excluded Grid Theorem
Zoom ID: 869 4632 6610 (ibsdimag)We study the Excluded Grid Theorem, a fundamental structural result in graph theory, that was proved by Robertson and Seymour in their seminal work on graph minors. The theorem states that there …
-
-
Chun-Hung Liu (劉俊宏), Asymptotic dimension of minor-closed families and beyond
Zoom ID:95464969835 (356260)The asymptotic dimension of metric spaces is an important notion in geometric group theory. The metric spaces considered in this talk are the ones whose underlying spaces are the vertex-sets …
-
-
Daniel Cranston, Vertex Partitions into an Independent Set and a Forest with Each Component Small
Zoom ID: 869 4632 6610 (ibsdimag)For each integer $k\ge 2$, we determine a sharp bound on $\operatorname{mad}(G)$ such that $V(G)$ can be partitioned into sets $I$ and $F_k$, where $I$ is an independent set and $G$ …
-
Meike Hatzel, Constant congestion bramble
Zoom ID: 869 4632 6610 (ibsdimag)In this talk I will present a small result we achieved during a workshop in February this year. My coauthors on this are Marcin Pilipczuk, Paweł Komosa and Manuel Sorge. A …