기초과학연구원 이산수학그룹
A family $\mathcal{F}$ of graphs is said to satisfy the Erdős-Pósa property if there exists a function $f$ such that for every positive integer $k$, every graph $G$ contains either …
We present a full characterization of the unavoidable induced subgraphs of graphs with large pathwidth. This consists of two results. The first result says that for every forest H, every …
In 1996, Reed, Robertson, Seymour and Thomas proved Younger's Conjecture, which states that for all directed graphs D, there exists a function f such that if D does not contain …
Since the proof of the graph minor structure theorem by Robertson and Seymour in 2004, its underlying ideas have found applications in a much broader range of settings than their …
The dimension of a poset is the least integer $d$ such that the poset is isomorphic to a subposet of the product of $d$ linear orders. In 1983, Kelly constructed …
By utilizing the recently developed hypergraph analogue of Godsil's identity by the second author, we prove that for all $n \geq k \geq 2$, one can reconstruct the matching polynomial …
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 $\mathbb{R}^d$ to …
A rooted spanning tree of a graph $G$ is called normal if the endvertices of all edges of $G$ are comparable in the tree order. It is well known that …
What causes a graph to have high chromatic number? One obvious reason is containing a large clique (a set of pairwise adjacent vertices). This naturally leads to investigation of \(\chi\)-bounded …