Mathematics Commons^™

H-Colouring Bipartite Graphs, John Engbers, David Galvin

Mathematics, Statistics and Computer Science Faculty Research and Publications

For graphs G and H, an H-colouring of G (or homomorphism from G to H) is a function from the vertices of G to the vertices of H that preserves adjacency. H-colourings generalize such graph theory notions as proper colourings and independent sets. For a given H, k∈V(H) and G we consider the proportion of vertices of G that get mapped to k in a uniformly chosen H-colouring of G. Our main result concerns this quantity when G is regular and bipartite. We find numbers 0⩽a−(k)⩽a+(k)⩽1 with the property that for all such G, with high probability the proportion is …