Maximising H-colourings of graphs

Journal article

For graphs G and H, an H-colouring of G is a map ψ : V (G) → V (H) such that ij ∈ 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 k(δ;H) such that, if n ≥ k(δ;H), the graph Kδ;n-δ max- imises 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 Kk;k as 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.

Authors: Guggiari, H; Scott, A

• Publication status: Published
• Peer review status: Peer reviewed
• Publisher: Wiley
• Journal: Journal of Graph Theory
• Volume: 92
• Issue: 2
• Pages: 172-185
• Publication date: 2019-01-11
• Acceptance date: 2018-11-18
• DOI: 10.1002/jgt.22446
• EISSN: 1097-0118
• ISSN: 0364-9024
• Keywords: H‐colouring; minimum degree; graph homomorphism