Homomorphisms of 3-chromatic graphs (Q1062066)

This paper presents a brief guide to graph homomorphisms (a homomorphism from G to H is a mapping f from V(G) to V(H) such that \((x,y)\in E(G)\Rightarrow (f(x),f(y))\in E(H)).\) Moreover the paper examines the effect of a homomorphism upon the chromatic difference sequence. This gives a necessary condition for the existence of a homomorphism from G to a vertex transitive H, extending the obvious condition \(\chi\) (H)\(\geq \chi (G)\). This is then used to show that iterated cartesian products of the Petersen graph produces an infinite family of vertex transitive 3- chromatic graphs, no one of which is a homomorphic image of any other.