A hill-climbing version of Vizing's theorem

Abstract

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 (2020), 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.

Vizing's theorem for signed multigraphs
You Lu, Jingru Zhao, Li Zhang
arXiv27 Sep 2026PreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv
A topological version of Huber's theorem
Ara Basmajian, Hugo Parlier
arXiv2 Sep 2026PreprintarXiv licenceFull textGeometry & topologyarXiv
On the causality of gravitational pp-wave spacetimes: A null version of Anderson's rigidity theorem
Hannah Cairo
arXiv1 Oct 2026PreprintarXiv licenceFull textGeometry & topology Gravitation & general relativityarXiv
A graded version of the separator theorem for planar graphs
Nabil H. Mustafa, Janos Pach
arXiv25 Oct 2026PreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
A counting version of Petersen's $2$-factor theorem
Hyunwoo Lee
arXiv7 Oct 2026PreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv

Cite

BibTeX RIS

BibTeX

@article{meyer2026hillclimbing,
  title = {{A hill-climbing version of Vizing's theorem}},
  author = {Lucas de Meyer and František Kardoš and Aurélie Lagoutte and Guillem Perarnau},
  journal = {Discrete Mathematics},
  year = {2026},
  month = nov,
  doi = {10.1016/j.disc.2026.115468},
  eprint = {2501.11541},
  archivePrefix = {arXiv},
  url = {https://hal.science/hal-05853232v1},
  note = {CC BY},
}

RIS

TY  - JOUR
TI  - A hill-climbing version of Vizing's theorem
AU  - Lucas de Meyer
AU  - František Kardoš
AU  - Aurélie Lagoutte
AU  - Guillem Perarnau
PY  - 2026
DA  - 2026/11/05
JO  - Discrete Mathematics
DO  - 10.1016/j.disc.2026.115468
UR  - https://hal.science/hal-05853232v1
AB  - 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 (2020), 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.
SN  - 0012-365X
ER  -

Abstract

Related

Cite