The Markov chain of colourings

DOI10.1007/3-540-59408-6_66MaRDI QIDQ5101430zbMATH OpenOpenAlexFDO

Authors J. E. Bartels, D. J. A. Welsh

Publication date 30 August 2022

Published in Integer Programming and Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/3-540-59408-6_66

zbMATH Keywords

chromatic numbermean colour number

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• On Markov chains for randomly H-coloring a graph
• A survey on the use of Markov chains to randomly sample colourings
• A more rapidly mixing Markov chain for graph colorings
• A Markov chain on the solution space of edge colorings of bipartite graphs
• scientific article; zbMATH DE number 4134071
• Markov chains and their application to hyperplane arrangement
• Colouring random graphs
• scientific article; zbMATH DE number 4101221
• scientific article; zbMATH DE number 4174001

Cites work

• A very simple algorithm for estimating the number of k‐colorings of a low‐degree graph
• Expansions of Chromatic Polynomials and Log-Concavity
• scientific article; zbMATH DE number 420886 (Why is no real title available?)
• scientific article; zbMATH DE number 4091530 (Why is no real title available?)
• On the computational complexity of the Jones and Tutte polynomials

Cited in

(12)

• Two chromatic polynomial conjectures
• Bounds for mean colour numbers of graphs
• Proof of a chromatic polynomial conjecture
• A note on the shameful conjecture
• Mean color numbers of some graphs
• A Markov chain on the solution space of edge colorings of bipartite graphs
• On Markov chains for randomly H-coloring a graph
• A survey on the use of Markov chains to randomly sample colourings
• A more rapidly mixing Markov chain for graph colorings
• Problems on chromatic polynomials of hypergraphs
• Markov random fields, Markov cocycles and the 3-colored chessboard
• Dominic Welsh: his work and influence

This page was built for publication: The Markov chain of colourings

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