기초과학연구원 이산수학그룹
Corneil, Olariu, and Stewart presented a recognition algorithm for interval graphs by six graph searches. Li and Wu simplified it to only four. The great simplicity of the latter algorithm …
The twin-width of a graph G can be defined as the least integer d such that there is a sequence of length |V(G)| of (strictly) coarser and coarser partitions of …
A pure pair in a graph G is a pair of subsets A, B of the vertex set of G such that in G, either all of the edges or …
For a graph G and an integer d, the dth power of G is the graph $G^d$ on the same vertex set as G where two vertices are considered adjacent …
A graph $G$ is semilinear of bounded complexity if the vertices of $G$ are elements of $\mathbb{R}^{d}$, and the edges of $G$ are defined by the sign patterns of $t$ …
Traditional clustering identifies groups of objects that share certain qualities. Tangles do the converse: they identify groups of qualities that typically occur together. They can thereby discover, relate, and structure …
The Grid Theorem of Robertson and Seymour is one of the most important tools in the field of structural graph theory, finding numerous applications in the design of algorithms for …
Given a graph, how do we construct a surface so that the graph embeds in that surface in an optimal way? Thomassen showed that for minimum genus as optimality criterion, …
Many problems that are NP-hard in general become tractable on `structurally recursive’ graph classes. For example, consider classes of bounded tree- or clique-width. Since the 1990s, many directed analogues of …
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 …