3 citations · 4 across the 13 of their papers we have counts for
17 papers
The tape reconfiguration problem and its consequences for dominating set reconfiguration
Nicolas Bousquet, Quentin Deschamps, Arnaud Mary +2
A dominating set of a graph is a set of vertices whose closed neighborhood is , i.e., . We view a dominating set as a collection of tokens plac…
How local constraints influence network diameter and applications to LCL generalizations
Nicolas Bousquet, Laurent Feuilloley, Théo Pierron
In this paper, we investigate how local rules enforced at every node can influence the topology of a network. More precisely, we establish several results on the diameter of trees…
Local certification of forbidden subgraphs
Nicolas Bousquet, Linda Cook, Laurent Feuilloley +2
Detecting specific structures in a network has been a very active theme of research in distributed computing for at least a decade. In this paper, we start the study of subgraph de…
Fast winning strategies for the attacker in eternal domination
Guillaume Bagan, Nicolas Bousquet, Nacim Oijid +1
Dominating sets in graphs are often used to model some monitoring of the graph: guards are posted on the vertices of the dominating set, and they can thus react to attacks occurrin…
Reconfiguration of plane trees in convex geometric graphs
Nicolas Bousquet, Lucas De Meyer, Théo Pierron +1
A non-crossing spanning tree of a set of points in the plane is a spanning tree whose edges pairwise do not cross. Avis and Fukuda in 1996 proved that there always exists a flip se…
A note on the flip distance between non-crossing spanning trees
Nicolas Bousquet, Valentin Gledel, Jonathan Narboni +1
We consider spanning trees of points in convex position whose edges are pairwise non-crossing. Applying a flip to such a tree consists in adding an edge and removing another so…
Extremal Independent Set Reconfiguration
Nicolas Bousquet, Bastien Durain, Théo Pierron +1
The independent set reconfiguration problem asks whether one can transform one given independent set of a graph into another, by changing vertices one by one in such a way the inte…
A note on highly connected -minor free graphs
Nicolas Bousquet, Théo Pierron, Alexandra Wesolek
We show that every -connected -minor free graph with minimum degree at least has maximum degree at most . As a consequence, we show that every 3-connected…
The smallest 5-chromatic tournament
Thomas Bellitto, Nicolas Bousquet, Adam Kabela +1
A coloring of a digraph is a partition of its vertex set such that each class induces a digraph with no directed cycles. A digraph is -chromatic if is the minimum number of…
Square coloring planar graphs with automatic discharging
Nicolas Bousquet, Lucas de Meyer, Quentin Deschamps +1
The discharging method is a powerful proof technique, especially for graph coloring problems. Its major downside is that it often requires lengthy case analyses, which are sometime…
What can be certified compactly?
Nicolas Bousquet, Laurent Feuilloley, Théo Pierron
Local certification consists in assigning labels (called \emph{certificates}) to the nodes of a network to certify a property of the network or the correctness of a data structure…
Strengthening a theorem of Meyniel
Quentin Deschamps, Carl Feghali, František Kardoš +2
For an integer and a graph , let be the graph that has vertex set all proper -colorings of , and an edge between two vertices and~ whe…
Improved square coloring of planar graphs
Nicolas Bousquet, Quentin Deschamps, Lucas de Meyer +1
Square coloring is a variant of graph coloring where vertices within distance two must receive different colors. When considering planar graphs, the most famous conjecture (Wegner,…
Wealth distribution in villages. Transition from socialism to capitalism in view of exhaustive wealth data and a master equation approach
István Gere, Szabolcs Kelemen, Tamás S. Biró +1
Socio-economic inequalities derived from an exhaustive wealth distribution is studied in a closed geographical region from Transylvania (Romania). Exhaustive wealth data is compute…
Local certification of MSO properties for bounded treedepth graphs
Nicolas Bousquet, Laurent Feuilloley, Théo Pierron
The graph model checking problem consists in testing whether an input graph satisfies a given logical formula. In this paper, we study this problem in a distributed setting, namely…
Local certification of graph decompositions and applications to minor-free classes
Nicolas Bousquet, Laurent Feuilloley, Théo Pierron
Local certification consists in assigning labels to the nodes of a network to certify that some given property is satisfied, in such a way that the labels can be checked locally. I…
(Sub)linear kernels for edge modification problems towards structured graph classes
Gabriel Bathie, Nicolas Bousquet, Théo Pierron
In a (parameterized) graph edge modification problem, we are given a graph , an integer and a (usually well-structured) class of graphs , and ask whether it is…