Premium
Maximizing H ‐Colorings of Connected Graphs with Fixed Minimum Degree
Author(s) -
Engbers John
Publication year - 2017
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.22105
Subject(s) - combinatorics , mathematics , bipartite graph , vertex (graph theory) , discrete mathematics , degree (music) , corollary , graph , physics , acoustics
Abstract For graphs G and H , an H ‐coloring of G is a map from the vertices of G to the vertices of H that preserves edge adjacency. We consider the following extremal enumerative question: for a given H , which connected n ‐vertex graph with minimum degree δ maximizes the number of H ‐colorings? We show that for nonregular H and sufficiently large n , the complete bipartite graph K δ , n − δis the unique maximizer. As a corollary, for nonregular H and sufficiently large n the graph K k , n − kis the unique k ‐connected graph that maximizes the number of H ‐colorings among all k ‐connected graphs. Finally, we show that this conclusion does not hold for all regular H by exhibiting a connected n ‐vertex graph with minimum degree δ that has more K q ‐colorings (for sufficiently large q and n ) than K δ , n − δ .