Promotion Talk by Chun-Hung Liu

Date: August 26, 2022

Time: 4:00PM - 5:00PM

Location: Bloc 117

Description: Title: Coarse graph colorings on minor-closed families
Abstract: Hadwiger's conjecture addresses graph minors and graph coloring and is widely considered as one of the most important open questions in graph theory. It states that the complete graph on t+1 vertices (i.e. the most obvious non-properly t-colorable graph) is a minor of any non-properly t-colorable graph. In this talk, we will present optimal results or nearly optimal results for coarse versions of Hadwiger's conjecture by relaxing the notion of proper coloring. Those versions are fundamental graph partitioning problems, and our results are incomparable with Hadwiger's conjecture and solve a number of open questions. Some of those versions are studied in other areas of mathematics.