A Markov chain on the solution space of edge-colorings of bipartite graphs

DOI10.1016/J.DAM.2023.01.029arXiv2103.11990MaRDI QIDQ6363454

Publication date: 22 March 2021

Abstract: In this paper, we exhibit an irreducible Markov chain

M

on the edge

k

-colorings of bipartite graphs based on certain properties of the solution space. We show that diameter of this Markov chain grows linearly with the number of edges in the graph. We also prove a polynomial upper bound on the inverse of acceptance ratio of the Metropolis-Hastings algorithm when the algorithm is applied on

M

with the uniform distribution of all possible edge

k

-colorings of

G

. A special case of our results is the solution space of the possible completions of Latin rectangles.

Mathematics Subject Classification ID

Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Orthogonal arrays, Latin squares, Room squares (05B15) Coloring of graphs and hypergraphs (05C15)

This page was built for publication: A Markov chain on the solution space of edge-colorings of bipartite graphs

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