Maximising H-colourings of graphs

Guggiari, H
Scott, A

1 January 2019

Journal:

Journal of Graph Theory

Last Updated:

2019-09-09T06:43:16.93+01:00

2

92

DOI:

10.1002/jgt.22446

172-185

abstract:

© 2019 Wiley Periodicals, Inc. 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 κ (δ, 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 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.

953282

Submitted

Journal Article