中央研究院數學研究所

Colloquium

Chromatic number and embeddings of graphs

2026/04/09 (Thu.) 15:30~16:30

Date : 2026/04/09 (Thu.) 15:30~16:30
Location : Seminar Room 617, Institute of Mathematics (NTU Campus)
Speaker : János Pach (Rényi Institute and EPFL)
Organizer : Bruce Reed (AS)
Abstract :
What makes the chromatic number of a graph large? There have been many attempts to answer this question. The most natural approach is to look for unavoidable substructures in graphs of large chromatic number. In 1943, Hadwiger made the conjecture that every graph of chromatic number r can be transformed into a complete graph of r vertices by a series of edge contractions and vertex and edge deletions. This is one of the most important unsolved problems in graph theory. After giving a somewhat biased survey of the problem, I plan to report on some related recent results.