기초과학연구원 이산수학그룹
We introduce a new subclass of chordal graphs that generalizes split graphs, which we call well-partitioned chordal graphs. Split graphs are graphs that admit a partition of the vertex set …
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 …
A notion of sublinear expander has played a central role in the resolutions of a couple of long-standing conjectures in embedding problems in graph theory, including e.g. the odd cycle …
A signed graph is a graph in which each edge has a positive or negative sign. Calling two graphs switch equivalent if one can get from one to the other …
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, …
A rooted digraph is a vertex-flame if for every vertex v there is a set of internally disjoint directed paths from the root to v whose set of terminal edges covers all …
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 …
A convex lattice polytope is the convex hull of a set of integral points. Vershik conjectured the existence of a limit shape for random convex lattice polygons, and three proofs …
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 …
Let $\mathbb{F}_q$ be a finite field of order $q$ which is a prime power. In the finite field setting, we say that a function $\phi\colon \mathbb{F}_q^d\times \mathbb{F}_q^d\to \mathbb{F}_q$ is a Mattila-Sjölin …