Speaker: Mingxian Zhong (Lehman College)
Title: Coloring graphs with forbidden induced subgraphs
Abstract: Graph coloring is a fundamental problem in graph theory and has a variety of applications. It is well known that deciding whether a graph can be colored within k colors is NP-complete for k>=3. Thus it is natural to ask that whether the complexity of the problem changes if we know that the input graph does not contain a particular induced subgraph, H. In this talk, I will first outline a polynomial-time algorithm which determines if an input graph containing no induced six-vertex path can be colored within 4 colors. Combined with previously known results this completes the classification of the complexity of the 4-coloring problem for graphs with a connected forbidden induced subgraph. This is joint work with Maria Chundnovsky and Sophie Spirkl. In the second part of this talk, I will characterize all graphs H for which there are only finitely many minimal non-three-colorable H-free graphs. This is joint work with Maria Chudnovsky, Jan Goedgebeur, and Oliver Schaudt.
More details are available on the seminar webpage