기초과학연구원 이산수학그룹
Hadwiger's famous coloring conjecture states that every t-chromatic graph contains a $K_t$-minor. Holroyd conjectured the following strengthening of Hadwiger's conjecture: If G is a t-chromatic graph and S⊆V(G) takes all …
A circle graph is an intersection graph of a set of chords of a circle. In this talk, I will describe the unavoidable induced subgraphs of circle graphs with large …
We show fixed-parameter tractability of the Directed Multicut problem with three terminal pairs (with a randomized algorithm). This problem, given a directed graph $G$, pairs of vertices (called terminals) $(s_1,t_1)$, …
We give a summary on the work of the last months related to Frankl's Union-Closed conjecture and its offsprings. The initial conjecture is stated as a theorem in extremal set …
Configurations of axis-parallel boxes in $\mathbb{R}^d$ are extensively studied in combinatorial geometry. Despite their perceived simplicity, there are many problems involving their structure that are not well understood. I will …