Homomorphisms

Although any isomorphism between two graphs is a homomorphism, the study of homomorphisms between graphs has quite a different flavour to the study of isomorphisms. In this chapter we support this claim by introducing a number of topics involving graph homomorphisms. We consider the relationship between homomorphisms and graph products, and in particular a famous unsolved conjecture of Hedetniemi, which asserts that if two graphs are not n-colourable, then neither is their product. Our second major topic is the exploration of the core of a graph, which is the minimal subgraph of a graph that is also a homomorphic image of the graph. Studying graphs that are equal to their core leads us to an interesting class of graphs first studied by Andrásfai. We finish the chapter with an exploration of the cores of vertex-transitive graphs.