Coloring graphs with forbidden induced subgraphs

NOV 09, 2018 | 11:45 PM



The Graduate Center
365 Fifth Avenue




November 09, 2018: 11:45 PM




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