Randomly coloring graphs of bounded treewidth

Shai Vardi

Type: Preprint

Publication Date: 2017-01-01

Citations: 3

DOI: https://doi.org/10.48550/arxiv.1708.02677

View Publication

Locations

arXiv (Cornell University) - View
DataCite API - View

Similar Works

Action	Title	Year	Authors
+	Improved bounds for sampling colorings	2000	Eric Vigoda
+	Perfectly Sampling $k\geq (8/3 +o(1))\Delta$-Colorings in Graphs	2020	Vishesh Jain Ashwin Sah Mehtaab Sawhney
+	Perfectly Sampling k\geq (8/3 +o(1))\Delta-Colorings in Graphs	2021	Vishesh Jain Ashwin Sah Mehtaab Sawhney
+	Perfectly Sampling $k\geq (8/3 +o(1))Δ$-Colorings in Graphs	2020	Vishesh Jain Ashwin Sah Mehtaab Sawhney
+ PDF Chat	Optimal Mixing for Randomly Sampling Edge Colorings on Trees Down to the Max Degree	2025	Charlie Carlson Xiaoyu Chen Weiming Feng Eric Vigoda
+	Perfect Sampling of graph $k$-colorings for $k> 3\Delta$	2019	Siddharth Bhandari Sayantan Chakraborty
+	Efficient and near-optimal algorithms for sampling connected subgraphs	2021	Marco Bressan
+ PDF Chat	Improved bounds for perfect sampling of k-colorings in graphs	2020	Siddharth Bhandari Sayantan Chakraborty
+ PDF Chat	On Sampling Colorings of Bipartite Graphs	2006	Rajalakshmi Balasubramanian C. R. Subramanian
+	Improved bounds for randomly colouring simple hypergraphs	2022	Weiming Feng Heng Guo Jiaheng Wang
+ PDF Chat	Optimal Mixing for Randomly Sampling Edge Colorings on Trees Down to the Max Degree	2024	Charlie Carlson Xiaoyu Chen Weiming Feng Eric Vigoda
+	Sampling colorings almost uniformly in sparse random graphs	2015	Yitong Yin Chihao Zhang
+	Improved Bounds for Perfect Sampling of $k$-Colorings in Graphs	2019	Siddharth Bhandari Sayantan Chakraborty
+	On Approximately Counting Colorings of Small Degree Graphs	1999	Russ Bubley Martin Dyer Catherine Greenhill Mark Jerrum
+	Improved bounds for perfect sampling of $k$-colorings in graphs.	2019	Siddharth Bhandari Sayantan Chakraborty
+ PDF Chat	Perfectly sampling <i>k</i> ≥ (8/3 + <i>o</i> (1))Δ-colorings in graphs	2021	Vishesh Jain Ashwin Sah Mehtaab Sawhney
+ PDF Chat	Randomly coloring planar graphs with fewer colors than the maximum degree	2007	Thomas P. Hayes Juan C. Vera Eric Vigoda
+	Randomly coloring planar graphs with fewer colors than the maximum degree	2007	Thomas P. Hayes Juan C. Vera Eric Vigoda
+	Faster algorithms for sampling connected induced subgraphs.	2020	Marco Bressan
+	Randomly coloring planar graphs with fewer colors than the maximum degree	2007	Thomas P. Hayes Juan C. Vera Eric Vigoda

Works That Cite This (3)

Action	Title	Year	Authors
+ PDF Chat	Improved Bounds for Randomly Sampling Colorings via Linear Programming	2019	Sitan Chen Michelle Delcourt Ankur Moitra Guillem Perarnau Luke Postle
+	Linear Programming Bounds for Randomly Sampling Colorings	2018	Sitan Chen Ankur Moitra
+	The Glauber dynamics for edge-colourings of trees	2018	Michelle Delcourt Marc Heinrich Guillem Perarnau

Works Cited by This (25)

Action	Title	Year	Authors
+	Improved bounds for sampling colorings	2003	Eric Vigoda
+	None	2006	Martin Dyer Abraham D. Flaxman Alan Frieze Eric Vigoda
+ PDF Chat	The Glauber Dynamics on Colorings of a Graph with High Girth and Maximum Degree	2004	Michael Molloy
+	None	2010	Paul Balister Béla Bollobás Joanne Johnson Mark Walters
+	An algorithm for the Tutte polynomials of graphs of bounded treewidth	1998	Artur Andrzejak
+	Random Walks on Truncated Cubes and Sampling 0-1 Knapsack Solutions	2004	Ben Morris Alistair Sinclair
+ PDF Chat	Absence of phase transition for antiferromagnetic Potts models via the Dobrushin uniqueness theorem	1997	Jesús Salas Alan D. Sokal
+	None	2010	Leslie Ann Goldberg Mark Jerrum Marek Karpiński
+	Randomly coloring graphs of girth at least five	2003	Thomas P. Hayes
+	Improved Bounds for Mixing Rates of Markov Chains and Multicommodity Flow	1992	Alistair Sinclair