33 citations · 94 across the 15 of their papers we have counts for
18 papers
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…
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…
The Canadian Traveller Problem on outerplanar graphs
Laurent Beaudou, Pierre Bergé, Vsevolod Chernyshev +5
We study the -Canadian Traveller Problem, where a weighted graph with a source and a target are given. This problem also has a hidden input $E_* \s…
Local certification of geometric graph classes
Oscar Defrain, Louis Esperet, Aurélie Lagoutte +2
The goal of local certification is to locally convince the vertices of a graph that satisfies a given property. A prover assigns short certificates to the vertices of the g…
Connected greedy colourings of perfect graphs and other classes: the good, the bad and the ugly
Laurent Beaudou, Caroline Brosse, Oscar Defrain +4
The Grundy number of a graph is the maximum number of colours used by the "First-Fit" greedy colouring algorithm over all vertex orderings. Given a vertex ordering $σ= v_1,\dots,v_…
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…
Efficient enumeration of maximal split subgraphs and induced sub-cographs and related classes
Caroline Brosse, Aurélie Lagoutte, Vincent Limouzy +2
In this paper, we are interested in algorithms that take in input an arbitrary graph , and that enumerate in output all the (inclusion-wise) maximal "subgraphs" of which ful…
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 …
Coloring graphs with no even hole : the triangle-free case
Aurélie Lagoutte
In this paper, we prove that the class of graphs with no triangle and no induced cycle of even length at least 6 has bounded chromatic number. It is well-known that even-hole-free…
Strong edge-coloring of -bipartite graphs
Julien Bensmail, Aurélie Lagoutte, Petru Valicov
A strong edge-coloring of a graph is an assignment of colors to edges such that every color class induces a matching. We here focus on bipartite graphs whose one part is of max…
Identifying codes in hereditary classes of graphs and VC-dimension
Nicolas Bousquet, Aurélie Lagoutte, Zhentao Li +2
An identifying code of a graph is a subset of its vertices such that every vertex of the graph is uniquely identified by the set of its neighbours within the code. We show a dichot…
Clique-Stable Set separation in perfect graphs with no balanced skew-partitions
Aurélie Lagoutte, Théophile Trunck
Inspired by a question of Yannakakis on the Vertex Packing polytope of perfect graphs, we study the Clique-Stable Set Separation in a non-hereditary subclass of perfect graphs. A c…
The complexity of Shortest Common Supersequence for inputs with no identical consecutive letters
Aurélie Lagoutte, Sébastien Tavenas
The Shortest Common Supersequence problem (SCS for short) consists in finding a shortest common supersequence of a finite set of words on a fixed alphabet Sigma. It is well-known t…
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…
Clique versus Independent Set
Nicolas Bousquet, Aurélie Lagoutte, Stéphan Thomassé
Yannakakis' Clique versus Independent Set problem (CL-IS) in communication complexity asks for the minimum number of cuts separating cliques from stable sets in a graph, called CS-…
2-FREE-FLOOD-IT is polynomial
Aurelie Lagoutte
We study a discrete diffusion process introduced in some combinatorial games called FLOODIT and MADVIRUS that can be played online and whose computational complexity has been recen…