33 citations · 94 across the 15 of their papers we have counts for
6 papers · 1 filter
Nowhere-zero flow reconfiguration
Louis Esperet, Kevin Hendrey, Aurélie Lagoutte +3
We initiate the study of nowhere-zero flow reconfiguration. The natural question is whether any two nowhere-zero -flows of a given graph are connected by a sequence of nowhe…
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…
Decomposition techniques applied to the Clique-Stable set Separation problem
Nicolas Bousquet, Aurélie Lagoutte, Frédéric Maffray +1
In a graph, a Clique-Stable Set separator (CS-separator) is a family of cuts (bipartitions of the vertex set) such that for every clique and every stable set …
The Erdős-Hajnal Conjecture for Paths and Antipaths
Nicolas Bousquet, Aurélie Lagoutte, Stéphan Thomassé
We prove that for every k, there exists such that every graph G on n vertices not inducing a path and its complement contains a clique or a stable set of size $n^{c_k…