## Document Type

Article

## Language

eng

## Format of Original

17 p.

## Publication Date

5-2012

## Publisher

Elsevier

## Source Publication

Journal of Combinatorial Theory, Series B

## Source ISSN

0095-8956

## Original Item ID

doi: 10.1016/j.jctb.2011.12.004

## Abstract

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 between a−(k) and a+(k), and we give examples where these extremes are achieved. For many H we have a−(k)=a+(k) for all k and so in these cases we obtain a quite precise description of the almost sure appearance of a randomly chosen H-colouring. As a corollary, we show that in a uniform proper q-colouring of a regular bipartite graph, if q is even then with high probability every colour appears on a proportion close to 1/q of the vertices, while if q is odd then with high probability every colour appears on at least a proportion close to 1/(q+1) of the vertices and at most a proportion close to 1/(q−1) of the vertices. Our results generalize to natural models of weighted H-colourings, and also to bipartite graphs which are sufficiently close to regular. As an application of this latter extension we describe the typical structure of H-colourings of graphs which are obtained from n-regular bipartite graphs by percolation, and we show that p=1/n is a threshold function across which the typical structure changes. The approach is through entropy, and extends work of J. Kahn, who considered the size of a randomly chosen independent set of a regular bipartite graph.

## Recommended Citation

Engbers, John and Galvin, David, "H-Colouring Bipartite Graphs" (2012). *Mathematics, Statistics and Computer Science Faculty Research and Publications*. 118.

https://epublications.marquette.edu/mscs_fac/118

## Comments

Accepted version.

Journal of Combinatorial Theory, Series B, Vol. 102, No. 3 (May 2012): 726-742. DOI.NOTICE: this is the author’s version of a work that was accepted for publication in

Journal of Combinatorial Theory, Series B. Changes resulting from the publishing process, such as peer review, editing, corrections, structural formatting, and other quality control mechanisms may not be reflected in this document. Changes may have been made to this work since it was submitted for publication. A definitive version was subsequently published inJournal of Combinatorial Theory, Series B, VOL 102, ISSUE 3, (May 2012). DOI.