Seminars in March 2018

  • Antoine Vigneron, Reachability in a Planar Subdivision with Direction Constraints
    Reachability in a Planar Subdivision with Direction Constraints
    Antoine Vigneron
    School of Electrical and Computer Engineering, UNIST, Ulsan, South Korea
    2018/3/27 Tue 5PM
    Given a planar subdivision with n vertices, each face having a cone of possible directions of travel, our goal is to decide which vertices of the subdivision can be reached from a given starting point s. We give an O(n log n)-time algorithm for this problem, as well as an Ω(n log n) lower bound in the algebraic computation tree model. We prove that the generalization where two cones of directions per face are allowed is NP-hard.
    Tags:

  • 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:

Monthly Archives