김린기

Archive of posts with tag '김린기'

  • Ringi Kim (김린기), Characterization of forbidden subgraphs for bounded star-chromatic number
    Characterization of forbidden subgraphs for bounded star-chromatic number
    Ringi Kim (김린기)
    Department of Mathematical Sciences, KAIST
    2018/3/6 Tue 5PM
    The chromatic number of a graph is the minimum k such that the graph has a proper k-coloring. It is known that if T is a tree, then every graph with large chromatic number contains T as a subgraph. In this talk, we discuss this phenomena for star-coloring (a proper coloring forbidding a bicolored path on four vertices) and acyclic-coloring (a proper coloring forbidding bicolored cycles). Specifically, we will characterize all graphs T such that every graph with sufficiently large star-chromatic number (acyclic-chromatic number) contains T as a subgraph.
    Tags:

  • Ringi Kim (김린기), Unavoidable subtournaments in tournaments with large chromatic number
    Unavoidable subtournaments in tournaments with large chromatic number
    Ringi Kim (김린기)
    University of Waterloo, Waterloo, Ontario, Canada
    2016/9/9 Fri 4PM-5PM
    For a tournament T, the chromatic number of T is the minimum number of transitive sets with union V(T). We say a set ? of tournaments is heroic if there exists c such that every tournament excluding all members of ? has chromatic number at most c. Berger et al. explicitly characterized all heroic sets of size one. In this talk, we study heroic sets of size two. This is a joint work with Maria Chudnovsky, Ilhee Kim, and Paul Seymour.
    Tags:

Monthly Archives