기초과학연구원 이산수학그룹
In this talk I will present a small result we achieved during a workshop in February this year. My coauthors on this are Marcin Pilipczuk, Paweł Komosa and Manuel Sorge. A bramble in an undirected graph $G$ is a family of connected subgraphs of $G$ such that for every two subgraphs $H_1$ and $H_2$ in the bramble either $V(H_1) \cap …
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)$, $(s_2,t_2)$, and $(s_3,t_3)$, and an integer $k$, asks to find a set of at most $k$ non-terminal vertices in $G$ that intersect all $s_1t_1$-paths, all …
Motivated by colouring minimal Cayley graphs, in 1978 Babai conjectured that no-lonely-colour graphs have bounded chromatic number. We disprove this in a strong sense by constructing graphs of arbitrarily large girth and chromatic number that have a proper edge colouring in which each cycle contains no colour exactly once. The result presented is the joint …