{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:38:08Z","timestamp":1787337488667,"version":"build-2736575974"},"reference-count":19,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[1999,1]]},"abstract":"<jats:p>We consider approximate counting of colorings of an n-vertex graph using rapidly mixing Markov chains. It has been shown by Jerrum and by Salas and Sokal that a simple random walk on graph colorings would mix rapidly, provided the number of colors k exceeded the maximum degree $\\Delta$ of the graph by a factor of at least 2. We prove that this is not a necessary condition for rapid mixing by considering the simplest case of 5-coloring graphs of maximum degree 3. Our proof involves a computer-assisted proof technique to establish rapid mixing of a new \"heat bath\" Markov chain on colorings using the method of path coupling. We outline an extension to 7-colorings of triangle-free 4-regular graphs. Since rapid mixing implies approximate counting in polynomial time, we show in contrast that exact counting is unlikely to be possible (in polynomial time). We give a general proof that the problem of exactly counting the number of proper k-colorings of graphs with maximum degree $\\Delta$ is $# P$-complete whenever $k\\geq 3$ and $\\Delta \\geq 3$.<\/jats:p>","DOI":"10.1137\/s0097539798338175","type":"journal-article","created":{"date-parts":[[2003,6,11]],"date-time":"2003-06-11T11:12:06Z","timestamp":1055329926000},"page":"387-400","source":"Crossref","is-referenced-by-count":24,"title":["On Approximately Counting Colorings of Small Degree Graphs"],"prefix":"10.1137","volume":"29","author":[{"given":"Russ","family":"Bubley","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Martin","family":"Dyer","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Catherine","family":"Greenhill","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Mark","family":"Jerrum","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,7,27]]},"reference":[{"key":"R1","doi-asserted-by":"crossref","unstructured":"D. Aldous,\n                      Random walks on finite groups and rapidly mixing Markov chains\n                      , in S\u00e9minaire de Probabilit\u00e9s XVII 1981\/1982, Lecture Notes in Math. 986, A. Dold and B. Eckmann, eds., Springer\u2010Verlag, New York, 1983, pp. 243\u2013297.","DOI":"10.1007\/BFb0068322"},{"key":"R2","doi-asserted-by":"publisher","DOI":"10.1090\/conm\/098"},{"key":"R3","doi-asserted-by":"crossref","unstructured":"R. Bubley and M. Dyer,\n                      Path coupling: A technique for proving rapid mixing in Markov chains\n                      , in 38th Annual Symposium on Foundations of Computer Science, Los Alamitos, CA, IEEE, 1997, pp. 223\u2013231.","DOI":"10.1109\/SFCS.1997.646111"},{"key":"R4","doi-asserted-by":"crossref","unstructured":"E. G. Coffman, D. S. Johnson, P. W. Shor, and R. R. Weber,\n                      Markov chains, computer proofs and average\u2010case analysis of best fit bin packing\n                      , in 25th Annual Symposium on the Theory of Computing, New York, ACM, 1993, pp. 412\u2013421.","DOI":"10.1145\/167088.167203"},{"key":"R5","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevD.21.2308"},{"key":"R6","doi-asserted-by":"publisher","DOI":"10.1145\/102782.102783"},{"key":"R7","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1999.1071"},{"key":"R8","doi-asserted-by":"publisher","unstructured":"Martin Dyer, Catherine Greenhill, A more rapidly mixing Markov chain for graph colorings, Proceedings of the Eighth International Conference \u201cRandom Structures and Algorithms\u201d (Poznan, 1997), Vol. 13, 1998, 285\u201331710.1002\/(SICI)1098-2418(199810\/12)13:3\/4<285:AID-RSA6>3.3.CO;2-U2000b:60168","DOI":"10.1002\/(SICI)1098-2418(199810\/12)13:3\/4<285::AID-RSA6>3.3.CO;2-U"},{"key":"R9","doi-asserted-by":"publisher","DOI":"10.1016\/0370-2693(87)91703-5"},{"key":"R10","unstructured":"C. Greenhill,\n                      The complexity of counting colorings and independent sets in sparse graphs and hypergraphs\n                      , Comput. Complexity, to appear."},{"key":"R11","doi-asserted-by":"publisher","DOI":"10.1017\/S0305004100068936"},{"key":"R12","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240070205"},{"key":"R13","doi-asserted-by":"publisher","DOI":"10.1137\/0218077"},{"key":"R14","unstructured":"M. Jerrum and A. Sinclair,\n                      The Markov chain Monte Carlo method: An approach to approximate counting and integration\n                      , in Approximation Algorithms for NP\u2010Hard Problems, D. Hochbaum, ed., PWS Publishing, Boston, 1996, pp. 482\u2013520."},{"key":"R15","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(86)90174-X"},{"key":"R16","unstructured":"B. Krek\u00f3,\n                      Linear Programming\n                      , Sir Isaac Pitman and Sons Ltd., London, 1968."},{"key":"R17","doi-asserted-by":"publisher","DOI":"10.1002\/9780470316511"},{"key":"R18","doi-asserted-by":"publisher","DOI":"10.1007\/BF02199113"},{"key":"R19","unstructured":"Bjarne Toft, Colouring, stable sets and perfect graphs, Elsevier, Amsterdam, 1995, 233\u201328897d:05123"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/S0097539798338175","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:13:31Z","timestamp":1787336011000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/S0097539798338175"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1999,1]]},"references-count":19,"journal-issue":{"issue":"2","published-print":{"date-parts":[[1999,1]]}},"alternative-id":["10.1137\/S0097539798338175"],"URL":"https:\/\/doi.org\/10.1137\/s0097539798338175","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[1999,1]]}}}