Extremal H-colorings of trees and 2-connected graphs

详细信息    查看全文

• 作者：John Engbers^a ; ¹ ; ^{john.engbers@marquette.edu} ; David Galvin^b ; ² ; ^{dgalvin1@nd.edu}
• 关键词：Graph homomorphisms ; H-coloring ; Graph coloring ; Widom&ndash ; Rowlinson model ; London&ndash ; Hoffman inequality ; 2-connected graphs
• 刊名：Journal of Combinatorial Theory, Series B
• 出版年：2017
• 出版时间：January 2017
• 年：2017
• 卷：122
• 期：Complete
• 页码：800-814
• 全文大小：380 K
• 卷排序：122

文摘

For graphs G and H, an H-coloring of G is an adjacency preserving map from the vertices of G to the vertices of H. H-colorings generalize such notions as independent sets and proper colorings in graphs. There has been much recent research on the extremal question of finding the graph(s) among a fixed family that maximize or minimize the number of H-colorings. In this paper, we prove several results in this area.First, we find a class of graphs HH with the property that for each H∈HH∈H, the n-vertex tree that minimizes the number of H  -colorings is the path PnPn. We then present a new proof of a theorem of Sidorenko, valid for large n, that for every H   the star K1,n−1K1,n−1 is the n-vertex tree that maximizes the number of H-colorings. Our proof uses a stability technique which we also use to show that for any non-regular H (and certain regular H  ) the complete bipartite graph K2,n−2K2,n−2 maximizes the number of H-colorings of n  -vertex 2-connected graphs. Finally, we show that the cycle CnCn has the most proper q-colorings among all n-vertex 2-connected graphs.