Journal article icon

Journal article

Maximising H-colourings of graphs

Abstract:

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...

Expand abstract
Publication status:
Published
Peer review status:
Peer reviewed
Version:
Accepted Manuscript

Actions


Access Document


Files:
Publisher copy:
10.1002/jgt.22446

Authors


More by this author
Institution:
University of Oxford
Division:
MPLS Division
Department:
Mathematical Institute
More by this author
Institution:
University of Oxford
Division:
MPLS Division
Department:
Mathematical Institute
Oxford college:
Merton College
ORCID:
0000-0003-4489-5988
Publisher:
Wiley Publisher's website
Journal:
Journal of Graph Theory Journal website
Volume:
92
Issue:
2
Pages:
172-185
Publication date:
2019-01-11
Acceptance date:
2018-11-18
DOI:
EISSN:
1097-0118
ISSN:
0364-9024
Pubs id:
pubs:953282
URN:
uri:fd1f8d9b-ab54-4477-8f40-b5ac2305e9d5
UUID:
uuid:fd1f8d9b-ab54-4477-8f40-b5ac2305e9d5
Local pid:
pubs:953282

Terms of use


Metrics



If you are the owner of this record, you can report an update to it here: Report update to this record

TO TOP