KAIST Advanced Institute for Science-X X : eXchange, X-disciplinary, eXplore, & unknown

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.