Maximising H ‐colourings of graphs

For graphs G and H , an H ‐colouring of G is a map ψ : V ( G ) → V ( H ) such that i j ∈ E ( G ) ⇒ ψ ( i ) ψ ( j ) ∈ E ( H ) . The number of H ‐colourings of G is denoted by hom ( G , H ) . We prove the following: for all graphs H and δ ≥ 3 , there is a constant κ ( δ , H ) such that, if n ≥ κ ( δ , H ) , the graph K δ , n − δmaximises the number of H ‐colourings among all connected graphs with n vertices and minimum degree δ . This answers a question of Engbers. We also disprove a conjecture of Engbers on the graph G that maximises the number of H ‐colourings when the assumption of the connectivity of G is dropped. Finally, let H be a graph with maximum degree k . We show that, if H does not contain the complete looped graph on k vertices or K k , kas a component and δ ≥ δ 0 ( H ) , then the following holds: for n sufficiently large, the graph K δ , n − δmaximises the number of H ‐colourings among all graphs on n vertices with minimum degree δ . This partially answers another question of Engbers.