Mathematics Commons^™

Extremal H-Colorings Of Trees And 2-Connected Graphs, John Engbers, David Galvin

Mathematics, Statistics and Computer Science Faculty Research and Publications

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 H with the property that for each H∈H, the n-vertex tree that minimizes the number of …