In graph theory, a graph is a set of vertices and edges, where each edge is a pair of vertices. A coloring of a graph is a function that assigns each vertex a color such that no two adjacent vertices share the same color. It is well known that deciding whether a graph can be colored within $k$-colors is NP-complete for $k\geq 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.
Mingxian Zhong