{"id":"arxiv/2605.05046","url":"https://arxiv.org/abs/2605.05046","tags":["cs.DM","math.PR"],"score":0,"title":"Sampling Simultaneous Edge-Colorings","domain":"cs.DM","source":"arxiv","authors":["Ezra Furtado-Tiwari","Eric Vigoda"],"reviews":0,"subject":"cs.DM","summary":"We study the sampling problem for simultaneous edge colorings. Given a pair of graphs $G_1=(V,E_1)$ and $G_2=(V,E_2)$ which are on the same vertex set $V$, a simultaneous edge coloring is an edge coloring of $G_1\\cup G_2$ so that each of the individual graphs is properly colored. When each of $G_1$ and $G_2$ are of maximum degree $Δ$, then it is conjectured that $Δ+2$ colors suffice, and recent work asymptotically establishes the conjecture. We study Markov chains for randomly sampling from the uniform distribution over simultaneous edge colorings. Straightforward applications of Jerrum's…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-05-06","reactions":{}}