Eunjin Oh (오은진), Feedback Vertex Set on Geometric Intersection Graphs
Room B232 IBS (기초과학연구원)I am going to present an algorithm for computing a feedback vertex set of a unit disk graph of size k, if it exists, which runs in time
10 events found.
Seminars and Colloquiums
Paul Seymour, Polynomial bounds for chromatic number
Zoom ID: 869 4632 6610 (ibsdimag)The Gyárfás-Sumner conjecture says that for every forest
Joonkyung Lee (이준경), Majority dynamics on sparse random graphs
Room B232 IBS (기초과학연구원)Majority dynamics on a graph
Donggyu Kim (김동규), 𝝘-graphic delta-matroids and their applications
Room B232 IBS (기초과학연구원)Bouchet (1987) defined delta-matroids by relaxing the base exchange axiom of matroids. Oum (2009) introduced a graphic delta-matroid from a pair of a graph and its vertex subset. We define a
Ben Lund, Maximal 3-wise intersecting families
Room B232 IBS (기초과학연구원)A family
Martin Milanič, Tree Decompositions with Bounded Independence Number
Zoom ID: 869 4632 6610 (ibsdimag)The independence number of a tree decomposition
Jaehoon Kim (김재훈), 2-complexes with unique embeddings in 3-space
Room B232 IBS (기초과학연구원)A well-known theorem of Whitney states that a 3-connected planar graph admits an essentially unique embedding into the 2-sphere. We prove a 3-dimensional analogue: a simply-connected 2-complex every link graph of which is 3-connected admits an essentially unique locally flat embedding into the 3-sphere, if it admits one at all. This can be thought of …
Sebastian Wiederrecht, Matching Minors in Bipartite Graphs
Zoom ID: 869 4632 6610 (ibsdimag)Matching minors are a specialisation of minors which preserves the existence and elementary structural properties of perfect matchings. They were first discovered as part of the study of the Pfaffian recognition problem on bipartite graphs (Polya's Permanent Problem) and acted as a major inspiration for the definition of butterfly minors in digraphs. In this talk …
Casey Tompkins, Ramsey numbers of Boolean lattices
Room B232 IBS (기초과학연구원)The poset Ramsey number
Tuukka Korhonen, Fast FPT-Approximation of Branchwidth
Zoom ID: 869 4632 6610 (ibsdimag)Branchwidth determines how graphs, and more generally, arbitrary connectivity (basically symmetric and submodular) functions could be decomposed into a tree-like structure by specific cuts. We develop a general framework for designing fixed-parameter tractable (FPT) 2-approximation algorithms for branchwidth of connectivity functions. The first ingredient of our framework is combinatorial. We prove a structural theorem establishing …