4 citations · 4 across the 2 of their papers we have counts for
4 papers
An algorithmic Vizing's theorem: toward efficient edge-coloring sampling with an optimal number of colors
Lucas De Meyer, František Kardoš, Aurélie Lagoutte +1
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 lar…
On Vizing's edge colouring question
Marthe Bonamy, Oscar Defrain, Tereza Klimošová +2
Soon after his 1964 seminal paper on edge colouring, Vizing asked the following question: can an optimal edge colouring be reached from any given proper edge colouring through a se…
Revisiting a theorem by Folkman on graph colouring
Marthe Bonamy, Pierre Charbit, Oscar Defrain +5
We give a short proof of the following theorem due to Jon H. Folkman (1969): The chromatic number of any graph is at most plus the maximum over all subgraphs of the difference…
Colouring perfect graphs with bounded clique number
Maria Chudnovsky, Aurélie Lagoutte, Paul Seymour +1
A graph is perfect if the chromatic number of every induced subgraph equals the size of its largest clique, and an algorithm of Grötschel, Lovász, and Schrijver from 1988 finds an…