A very simple algorithm for estimating the number of k‐colorings of a low‐degree graph
Author:
- 1 September 1995
- journal article
- research article
- Published by Wiley in Random Structures & Algorithms
- Vol. 7 (2) , 157-165
Abstract
A fully polynomial randomized approximation scheme is presented for estimating the number of (vertex) k‐colorings of a graph of maximum degree Δ, when k ≥ 2Δ + 1. © 1995 John Wiley & Sons, Inc.Keywords
This publication has 7 references indexed in Scilit:
- Comment on ‘‘Antiferromagnetic Potts models’’Physical Review Letters, 1993
- Group representations in probability and statistics1988
- Random generation of combinatorial structures from a uniform distributionTheoretical Computer Science, 1986
- Random walks on finite groups and rapidly mixing markov chains1983
- Decay of correlations in classical lattice models at high temperatureCommunications in Mathematical Physics, 1979
- Some simplified NP-complete graph problemsTheoretical Computer Science, 1976
- On colouring the nodes of a networkMathematical Proceedings of the Cambridge Philosophical Society, 1941