H-colouring bipartite graphs

DOI10.1016/J.JCTB.2011.12.004zbMATH Open1248.05188arXiv1101.0839OpenAlexW2018614962MaRDI QIDQ414646FDOQ414646

Authors: John Engbers, David Galvin 

Publication date: 11 May 2012

Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Abstract: For graphs $G$ and $H$, an {em $H$-colouring} of $G$ (or {em 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$, $kinV(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 $0leq{a}^{-}(k)leq{a}^{+}(k)leq1$ 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.

Full work available at URL: https://arxiv.org/abs/1101.0839

Recommendations

• Maximizing \(H\)-colorings of a regular graph
• \(H\)-coloring tori
• Maximising \(H\)-colourings of graphs
• Coloring complete bipartite graphs from random lists
• Counting colorings of a regular graph

zbMATH Keywords

graph homomorphismsgraph colouringrandom bipartite graph

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Coloring of graphs and hypergraphs (05C15) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Cites Work

• The probabilistic method. With an appendix on the life and work of Paul Erdős.
• Title not available (Why is that?)
• Some intersection theorems for ordered sets and graphs
• An entropy approach to the hard-core model on bipartite graphs
• On weighted graph homomorphisms
• Title not available (Why is that?)
• Title not available (Why is that?)
• Random surfaces with two-sided constraints: An application of the theory of dominant ground states
• Graph homomorphisms and phase transitions
• The multistate hard core model on a regular tree
• Markov random field models of multicasting in tree networks
• Asymptotics and random matrices with row-sum and column sum-restrictions
• Range of cube-indexed random walk

Cited In (10)

• Homomorphisms from the torus
• Maximizing \(H\)-colorings of a regular graph
• \(H\)-coloring tori
• Lipschitz functions on expanders are typically flat
• The independent set sequence of regular bipartite graphs
• Homomorphisms of trees into a path
• Extremal H‐Colorings of Graphs with Fixed Minimum Degree
• Title not available (Why is that?)
• Maximising \(H\)-colourings of graphs
• Rigidity of proper colorings of \(\mathbb{Z}^d \)

This page was built for publication: \(H\)-colouring bipartite graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q414646)