기초과학연구원 이산수학그룹
For given $k$ graphs $G_1,\dots, G_k$ over a common vertex set of size $n$, what conditions on $G_i$ ensures a 'colorful' copy of $H$, i.e. a copy of $H$ containing …
Graph Minor project by Robertson and Seymour is perhaps the deepest theory in Graph Theory. It gives a deep structural characterization of graphs without any graph $H$ as a minor. …
In a reduction sequence of a graph, vertices are successively identified until the graph has one vertex. At each step, when identifying $u$ and $v$, each edge incident to exactly …
Our talk will mainly focus on the relationship between substructures and eigenvalues of graphs. We will briefly survey recent developments on a conjecture of Bollobás and Nikiforov and a classical …
Erdős and Pósa proved in 1965 that there is a duality between the maximum size of a packing of cycles and the minimum size of a vertex set hitting all …
We prove that there is a function $f : \mathbb{N} \to \mathbb{N}$ such that for every function $g : \mathbb{N} \to \mathbb{N} \cup \{\infty\}$ with $g(1)=1$ and $g \ge f$, …
An independent dominating set of a graph, also known as a maximal independent set, is a set $S$ of pairwise non-adjacent vertices such that every vertex not in $S$ is …
A graph G is a k-leaf power if there exists a tree T whose leaf set is V(G), and such that uv is an edge if and only if the …
Tutte (1961) proved that every simple $3$-connected graph $G$ has an edge $e$ such that $G \setminus e$ or $G / e$ is simple $3$-connected, unless $G$ is isomorphic to …
Every minor-closed class of matroids of bounded branch-width can be characterized by a minimal list of excluded minors, but unlike graphs, this list could be infinite in general. However, for …