References

In this talk we review some general necessary conditions for the existence of graph ho-momorphisms [1, 4, 5]. Also we introduce some algebraic no-homomorphism theorems [1, 2, 3]. On the other hand, we will consider natural matrices related to graphs (e.g. the adjacency matrix and the combinatorial Laplacian) and we introduce necessary conditions for the existence of graph homomorphisms in terms of their spectra. Also, we apply nodal domain theory, that shows how one can consider the sign-graphs of the corresponding eigenfunctions to obtain nohomomorphism criteria. In this regard, we present some necessary conditions for the spanning subgraph prob-lem, that also provides a generalization of a theorem of Mohar [5] as a necessary condi-tion for Hamiltonicity. In particular, in the case that the range is a Cayley graph or an edge-transitive graph, we recall theorems with a corollary about the existence of homo-morphisms to cycles. This, specially, provides a proof of the fact that the Coxeter graph is a core. Index Words: graph eigenvalue, graph homomorphism, graph colouring