기초과학연구원 이산수학그룹
In 2015, Kawarabayashi and Kreutzer proved the directed grid theorem. The theorem states the existence of a function f such that every digraph of directed tree-width f(k) contains a cylindrical …
We solve a long-standing open problem posed by Goodman and Pollack in 1988 by establishing a necessary and sufficient condition for a finite family of convex sets in
A rooted spanning tree of a graph
Let S and T be two sets of points in a metric space with a total of n points. Each point in S and T has an associated value that specifies an upper limit on how many points it can …
Given a tournament
A seminal result of Tutte asserts that every 4-connected planar graph is hamiltonian. By Wagner's theorem, Tutte's result can be restated as: every 4-connected graph with no