H-colouring bipartite graphs

DOI10.1016/J.JCTB.2011.12.004MaRDI QIDQ414646zbMATH OpenOpenAlexFDO

Authors John Engbers, David Galvin

Publication date 11 May 2012

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

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

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)

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.

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

Cites work

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

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
• scientific article; zbMATH DE number 3933100 (Why is no real title available?)
• Rigidity of proper colorings of \(\mathbb{Z}^d \)
• Maximising \(H\)-colourings of graphs

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)