기초과학연구원 이산수학그룹
Computationally hard problems have been widely used to construct cryptographic primitives such as encryptions, digital signatures. For example, provably secure primitives are based on a reduction from the hardness problems. …
The fractional Helly theorem is a simple yet remarkable generalization of Helly's classical theorem on the intersection of convex sets, and it is of considerable interest to extend the fractional Helly …
Pósa's theorem states that any graph G whose degree sequence $d_1\leq \dots \leq d_n$ satisfies $d_i \geq i+1$ for all $i< n/2$ has a Hamilton cycle. This degree condition is …
A weak order is a way to rank n objects where ties are allowed. Weak orders have applications in diverse areas such as linguistics, designing combination locks, and even in …
Online list coloring and DP-coloring are generalizations of list coloring that attracted considerable attention recently. Each of the paint number, $\chi_P(G)$, (the minimum number of colors needed for an online …
For given graphs $G$ and $F$, the Turán number $ex(G,F)$ is defined to be the maximum number of edges in an $F$-free subgraph of $G$. Briggs and Cox introduced a …
Oftentimes in chromatic graph theory, precoloring techniques are utilized in order to obtain the desired coloring result. For example, Thomassen's proof for 5-choosability of planar graphs actually shows that two adjacent …
Given a graph class $\mathcal{H}$, the task of the $\mathcal{H}$-Square Root problem is to decide whether an input graph G has a square root H that belongs to $\mathcal{H}$. We …
We present a new technique for designing fixed-parameter algorithms for graph cut problems in undirected graphs, which we call flow augmentation. Our technique is applicable to problems that can be …
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. …