## Theory of Combinatorial Algorithms

Prof. Emo Welzl and Prof. Bernd Gärtner

# Mittagsseminar (in cooperation with M. Ghaffari, A. Steger and B. Sudakov)

 Mittagsseminar Talk Information

Date and Time: Thursday, January 10, 2013, 12:15 pm

Duration: 30 minutes

Location: CAB G51

Speaker: Jan Foniok (Queen's University)

## Adjoint functors in graph theory

Theorem (Geller, Stahl): Let G be a graph. Then the lexicographic product G[K2] is n-colourable if and only if G admits a homomorphism to the Kneser graph K(n,2).

Theorem (El-Zahar, Sauer): For two graphs G and H, the categorial product G × H is n-colourable if and only if G admits a homomorphism to the exponential graph KnH.

What do these two theorems have in common? Each is an example of the same phenomenon, known in category theory as adjoint functors. I will explain what they are and show some other applications, such as a circular version of the Gallai–Roy (–Hasse–Vitaver) Theorem.

Information for students and suggested topics for student talks