기초과학연구원 이산수학그룹
On March 3, 2026, Chính T. Hoàng from the Wilfrid Laurier University, Waterloo, Canada gave a survey talk on graph coloring and forbidden induced subgraphs at the Discrete Math Seminar. The title of his talk was “Problems on graph coloring“.
A k-coloring of a graph is an assignment of k colors to its vertices such that no two adjacent adjacent vertices receive the same color. The Coloring Problem is the problem of determining the smallest k such that the graph admits a k-coloring. Given a set L of graphs, a graph G is L-free if G does not contain any graph in L as an induced subgraph. The complexity of the Coloring Problem for L-free graphs is known (NP-complete or polynomial-time solvable) whenever L contains a single graph. There has been keen interest in coloring graphs whose forbidden list L contains basic graphs such as induced paths, induced cycles and their complements. In this talk, I will provide a survey of recent progress on this topic.