An algorithmic Vizing's theorem: toward efficient edge-coloring sampling with an optimal number of colors
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866917898375659520 |
|---|---|
| author | De Meyer, Lucas Kardoš, František Lagoutte, Aurélie Perarnau, Guillem |
| author_facet | De Meyer, Lucas Kardoš, František Lagoutte, Aurélie Perarnau, Guillem |
| contents | The problem of sampling edge-colorings of graphs with maximum degree $Δ$ has received considerable attention and efficient algorithms are available when the number of colors is large enough with respect to $Δ$. Vizing's theorem guarantees the existence of a $(Δ+1)$-edge-coloring, raising the natural question of how to efficiently sample such edge-colorings. In this paper, we take an initial step toward addressing this question. Building on the approach of Dotan, Linial, and Peled, we analyze a randomized algorithm for generating random proper $(Δ+1)$-edge-colorings, which in particular provides an algorithmic interpretation of Vizing's theorem. The idea is to start from an arbitrary non-proper edge-coloring with the desired number of colors and at each step, recolor one edge uniformly at random provided it does not increase the number of conflicting edges (a potential function will count the number of pairs of adjacent edges of the same color). We show that the algorithm almost surely produces a proper $(Δ+1)$-edge-coloring and propose several conjectures regarding its efficiency and the uniformity of the sampled colorings. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2501_11541 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | An algorithmic Vizing's theorem: toward efficient edge-coloring sampling with an optimal number of colors De Meyer, Lucas Kardoš, František Lagoutte, Aurélie Perarnau, Guillem Data Structures and Algorithms Discrete Mathematics 05C15, 05C81 G.2.2; F.2.2 The problem of sampling edge-colorings of graphs with maximum degree $Δ$ has received considerable attention and efficient algorithms are available when the number of colors is large enough with respect to $Δ$. Vizing's theorem guarantees the existence of a $(Δ+1)$-edge-coloring, raising the natural question of how to efficiently sample such edge-colorings. In this paper, we take an initial step toward addressing this question. Building on the approach of Dotan, Linial, and Peled, we analyze a randomized algorithm for generating random proper $(Δ+1)$-edge-colorings, which in particular provides an algorithmic interpretation of Vizing's theorem. The idea is to start from an arbitrary non-proper edge-coloring with the desired number of colors and at each step, recolor one edge uniformly at random provided it does not increase the number of conflicting edges (a potential function will count the number of pairs of adjacent edges of the same color). We show that the algorithm almost surely produces a proper $(Δ+1)$-edge-coloring and propose several conjectures regarding its efficiency and the uniformity of the sampled colorings. |
| title | An algorithmic Vizing's theorem: toward efficient edge-coloring sampling with an optimal number of colors |
| topic | Data Structures and Algorithms Discrete Mathematics 05C15, 05C81 G.2.2; F.2.2 |
| url | https://arxiv.org/abs/2501.11541 |