KAIX Challenge

KAIST Advanced Institute for Science-X

• 
  김재훈 교수

  • 카이스트 수리과학과
  • jaehoon.kim@kaist.ac.kr
• Research area

  Extremal problems in graph theory

• Brief

  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.