Showing cs.DMShow all
3 papers · 1 filter
cs.DM2026
Sampling Simultaneous Edge-Colorings
Ezra Furtado-Tiwari, Eric Vigoda
We study the sampling problem for simultaneous edge colorings. Given a pair of graphs and which are on the same vertex set , a simultaneous edge colo…
cs.DM2024
Optimal Mixing for Randomly Sampling Edge Colorings on Trees Down to the Max Degree
Charlie Carlson, Xiaoyu Chen, Weiming Feng +1
We address the convergence rate of Markov chains for randomly generating an edge coloring of a given tree. Our focus is on the Glauber dynamics which updates the color at a randoml…
cs.DM2024
Flip Dynamics for Sampling Colorings: Improving Using a Simple Metric
Charlie Carlson, Eric Vigoda
We present improved bounds for randomly sampling -colorings of graphs with maximum degree ; our results hold without any further assumptions on the graph. The Glauber dynamic…