Some questions about colourings and homomorphisms of categorical products of graphs can be approached by proving the existence of homomorphisms from exponential graphs into target graphs.

I will present two specific instances:

- El-Zahar and Sauer’s proof that the chromatic number of the product of two 4- chromatic graphs is 4.

- The density of the lattice of powers of a fixed complete graph in the category of directed graphs.

In both cases, the proof relies on homomorphisms whose existence is not established constructively but rather dually, by proving the nonexistence of homomorphism from obstructions to the domain. This requires a suitable characterisation of the obstructions to a structure with bounded width.