8 papers
Determining a graph from its reconfiguration graph
Gaétan Berthe, Caroline Brosse, Brian Hearn +3
Given a graph and a natural number , the -recolouring graph is the graph whose vertices are the -colourings of and whose edges link pairs of col…
The Graph Coloring Game on -Grids
Caroline Brosse, Nicolas Martins, Nicolas Nisse +1
The graph coloring game is a famous two-player game (re)introduced by Bodlaender in . Given a graph and , Alice and Bob alternately (starting with Alice…
Output-Sensitive Enumeration of Potential Maximal Cliques in Polynomial Space
Caroline Brosse, Alessio Conte, Vincent Limouzy +2
A set of vertices in a graph forms a potential maximal clique if there exists a minimal chordal completion in which it is a maximal clique. Potential maximal cliques were first int…
On the hardness of inclusion-wise minimal separators enumeration
Caroline Brosse, Oscar Defrain, Kazuhiro Kurita +3
Enumeration problems are often encountered as key subroutines in the exact computation of graph parameters such as chromatic number, treewidth, or treedepth. In the case of treedep…
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_…
Locating Dominating Sets in local tournaments
Thomas Bellitto, Caroline Brosse, Benjamin Lévêque +1
A dominating set in a directed graph is a set of vertices such that all the vertices that do not belong to have an in-neighbour in . A locating set is a set of verti…
Polynomial delay algorithm for minimal chordal completions
Caroline Brosse, Vincent Limouzy, Arnaud Mary
Motivated by the problem of enumerating all tree decompositions of a graph, we consider in this article the problem of listing all the minimal chordal completions of a graph. In \c…
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…