Title    name
2018 Discrete Math 세미나
 
  Title
  Speaker 김린기
  Date 2018-03-06
  Host
  Place KAIST
  File  의 1 번째 Real Media 동영상입니다.
 
Abstract : 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.