Tutte Colloquium - Chinh T. Hoang

Title: The coloring problem for restricted graph classes

Abstract:

Let L be a set of graphs. Free(L) is the set of graphs that do not contain any graph in L as an induced subgraph. It is known that if L is a set of four-vertex graphs, then the complexity of the coloring problem for Free(L) is known with three exceptions: L = {claw, 4K₁}, L = {claw, 4K₁, co-diamond}, and L = {C4, 4K₁}. We discuss the state of knowledge on these three problems.