Ringi Kim (김린기), Characterization of forbidden subgraphs for bounded star-chromatic number

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.