33 citations · 94 across the 15 of their papers we have counts for
9 papers · 1 filter
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_…
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…
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…
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-…