Joar Bagge: Graph coloring: theory and applications

Tid: Fr 2019-02-22 kl 15.15 - 16.00

Föreläsare: Joar Bagge

Plats: Room 3418, Lindstedtsvägen 25, 4th floor, Department of Mathematics, KTH

How many colors are needed to color a map of countries, without giving any country the same color as one of its neighbours? Would the answer be different if we were living on a torus rather than a sphere? What does this have to do with graph theory?

In this talk we will give some historical background to the map coloring problem, and explain its connection to graph theory. It turns out that sudoku puzzles and scheduling can also be seen as graph coloring problems. Finally, we introduce a greedy algorithm that can color any graph in an optimal way, but maybe not on the first try.

This talk is based on material from Stockholms Matematiska Cirkel 2018/2019, a course given to Swedish high school students by KTH/SU. No prior knowledge of graph theory is assumed