KAIST Advanced Institute for Science-X
- 카이스트 수리과학과
Extremal problems in graph theory
This project aims to conduct research on various extremal problems in graph theory. In particular, finding specific structures in a complicated graphs are one of main research topics. For example, together with Dr. Joos, I recently proved a rainbow version of Dirac’s theorem. A classical theorem of Dirac states that the one can find a Hamiltonian cycle (a cycle covering all vertices) in an n-vertex graph with minimum degree at least n/2. Instead of considering just one graph, we consider a collection of n graphs on the same vertex set. We prove that if all graphs have minimum degree at least n/2, then one can find a Hamiltonian cycle consisting of one edge from each of the n graphs.