기초과학연구원 이산수학그룹
On May 26, 2021, Dimitrios M. Thilikos from LIRMM, CNRS gave an online talk at the Virtual Discrete Math Colloquium about an upper bound of the size of obstructions for minor-closed classes of graphs at the Virtual Discrete Math Colloquium. The title of the talk was “Bounding Obstructions sets: the cases of apices of minor closed classes“.
Given a minor-closed graph class ${\cal G}$, the (minor) obstruction of ${\cal G}$ is the set of all minor-minimal graphs not in ${\cal G}$. Given a non-negative integer $k$, we define the $k$-apex of ${\cal A}$ as the class containing every graph $G$ with a set $S$ of vertices whose removal from $G$ gives a graph on ${\cal G}$. We prove that every obstruction of the $k$-apex of ${\cal G}$ has size bounded by some 4-fold exponential function of $p(k)$ where p is a polynomial function whose degree depends on the size of the minor-obstructions of ${\cal G}$. This bound drops to a 2-fold exponential one when ${\cal G}$ excludes some apex graph as a minor (i.e., a graph in the $1$-apex of planar graphs).
Joint work with Ignasi Sau and Giannos Stamoulis.