기초과학VOD

BASIC SCI VOD

  •   >  
  • 연구동향
  •   >  
  • 기초과학VOD
Super Title 2018 Discrete Math 세미나
Title Characterization of forbidden subgraphs for bounded star-chromatic number
Speaker 김린기  (  KAIST  ) Date 2018-03-06
Host KAIST Place KAIST
VOD    
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.

이 페이지에서 제공하는 정보에 만족하십니까?