Mathematical Sciences Colloquium

In 1951 de Bruijn and Erdös proved that an infinite graph is n-colourable if and only if each of its finite subgraphs is n- colourable. This is often referred to as 'compactness of n-colouring'. Using the fact that n-colouring is essentially identical to finding a graph homomorphism to a complete graph on n vertices, we say that a graph G is homomorphically compact if each infinite graph H admits a homomorphism to G exactly when all of its finite subgraphs admit such a homomorphism.

We will show that (really) infinite compact graphs exist and explore various other problems related to them.