Open Research Index

Sampling Simultaneous Edge-Colorings

Ezra Furtado-Tiwari, Eric Vigoda

arXivarxiv/2605.05046May 6, 2026cs.DMscore 0

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…

SourceJSON

Comments and reviews

No comments yet.

Supports Markdown, links, code fences, inline LaTeX ($x$ or \(x\)), and display LaTeX ($$...$$ or \[...\]).

Drafts stay in this tab.

API

curl /api/v1/records/arxiv/2605.05046
curl -X POST /api/v1/records/arxiv/2605.05046/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2605.05046/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'