Problems on graph colouring

Seminario Súmate

Chính T. Hoàng

• Wilfried Laurier University

---

08 SEP 2026

13:00 h.

Anfiteatro Alfredo Barrera

---

The Coloring Problem is to decide if a given graph can be colored with at most k colors, given an integer k, such that no two adjacent adjacent vertices receive the same color. 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 on L-free graphs is known 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, in- duced cycles and their complements. In this talk, I will provide a survey of recent progress on this topic.

---

Informes: rpm@ciencias.unam.mx