기초과학연구원 이산수학그룹
Forbidden graph characterizations provide a convenient way of specifying graph classes, which often exhibit a rich combinatorial and algorithmic theory. A prime example in graph theory are classes of bounded …
Generalized extremal problems have been one of the central topics of study in extremal combinatorics throughout the last few decades. One such simple-looking problem, maximizing the number of cliques of …
In 1943, Hadwiger conjectured that every graph with no $K_t$ minor is $(t-1)$-colorable for every $t\ge 1$. In the 1980s, Kostochka and Thomason independently proved that every graph with no $K_t$ …
Let $G$ be a graph on the vertex set $V$. A vertex subset $W \subset V$ is a cover of $G$ if $V \setminus W$ is an independent set of …
We study the Excluded Grid Theorem, a fundamental structural result in graph theory, that was proved by Robertson and Seymour in their seminal work on graph minors. The theorem states that there …
Let $G$ be a graph on $V$ and $n$ a positive integer. Let $I_n(G)$ be the abstract simplicial complex whose faces are the subsets of $V$ that do not contain …
This lecture series covers several different techniques on embedding paths/trees/cycles in (pseudo)random graphs/expanders as (induced) subgraphs.
This lecture series covers several different techniques on embedding paths/trees/cycles in (pseudo)random graphs/expanders as (induced) subgraphs.
This lecture series covers several different techniques on embedding paths/trees/cycles in (pseudo)random graphs/expanders as (induced) subgraphs.
This lecture series covers several different techniques on embedding paths/trees/cycles in (pseudo)random graphs/expanders as (induced) subgraphs.