33 citations · 242 across the 67 of their papers we have counts for
23 papers · 1 filter
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…
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…
Chordal directed graphs are not -bounded
Pierre Aboulker, Nicolas Bousquet, Rémi de Verclos
We show that digraphs with no transitive tournament on vertices and in which every induced directed cycle has length can have arbitrarily large dichromatic number. This ans…
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,…
Locating-dominating sets: from graphs to oriented graphs
Nicolas Bousquet, Quentin Deschamps, Tuomo Lehtilä +1
A locating-dominating set in an undirected graph is a subset of vertices such that is dominating and for every , we have . In this p…