Nicolas Bousquet
|
|
|
|
|
nicolas.bousquet@grenoble-inp.fr |
CNRS Researcher, G-SCOP, Grenoble, France. |
Bureau H327 |
Formerly, I was an ATER (temporary assistant professor position) in Ecole Centrale de Lyon during the academic year 2015-2016. I was a member of the LIRIS laboratory in the GOAL (Graphes, AlgOrithmes et AppLications) team. Before, I was a postodoctoral fellow at the Department of Mathematics and Statistics at McGill University where I worked with Adrian Vetta. My scholarship was partially funded by the GERAD (Groupe d'études et de recherche en analyse des décisions) at Université de Montréal.
I have defended my PhD the 9-th of December 2013 under the direction of Stéphane Bessy and Stéphan Thomassé at the Université Montpellier 2 (LIRMM). Its title was "Hitting sets, VC-dimension and Multicut". The manuscript can be found there and the slides of the defense can be found there.
I am interested in graph theory, game theory and combinatorics.
My topics of research include but are not limited to:
icon. To access to the slides of the presentations, click on the 
icon. When already available online, you can access to the paper on the editor webpage via the icon 
.
A proof of the Erdos-Sands-Sauer-Woodrow conjecture, with William Lochet and Stéphan Thomassé, to appear in Journal on Combinatorial Theory, Ser. B.
Exact distance coloring in trees, with Louis Esperet, Ararat Harutyunyan and Rémi de Joannis de Verclos. Chi-bounded families of oriented graphs, with Pierre Aboulker, Jorgen Bang-Jensen, Pierre Charbit, Frédéric Havet, Frédéric Maffray and José Zamora. Recoloring graphs via tree-decompositions, with Marthe Bonamy. On a conjecture of Mohar concerning Kempe equivalence, with Marthe Bonamy, Carl Feghali and Matthew Johnson. Multicut is FPT, with Jean Daligault and Stéphan Thomassé. Decomposition techniques applied to the Clique-Stable set Separation problem, with Aurélie Lagoutte, Frédéric Maffray and Lucas Pastor.
A Vizing-like theorem for union vertex-distinguishing edge coloring, with Antoine Dailly, Eric Duchêne, Hamamache Kheddouci et Aline Parreau.
Colourful paths for 3-chromatic graphs, with Stéphane Bessy.
Fast recoloring of sparse graphs, with Guillem Perarnau.
The Erdos-Hajnal Conjecture for long holes and antiholes, with Marthe Bonamy and Stéphan Thomassé.
Identifying codes in hereditary classes of graphs and VC-dimension, with Aurélie Lagoutte, Zhentao Li, Aline Parreau and Stéphan Thomassé.
VC-dimension and Erdös-Pósa property, with Stéphan Thomassé.
The Erdos-Hajnal Conjecture for Paths and Antipaths, with Aurélie Lagoutte and Stéphan Thomassé.
Excluding cycles with a fixed number of chords, with Pierre Aboulker. 
]
Clique versus independent set, with Aurélie Lagoutte and Stéphan Thomassé. ]
Brooks' theorem on powers of graphs, with Marthe Bonamy. ]
Parameterized Domination in Circle Graphs, with Daniel Gonçalves, George Mertzios, Christophe Paul, Ignasi Sau and Stéphan Thomassé. ]
Scott's induced subdivision conjecture for maximal triangle-free graphs, with Stéphan Thomassé.]
EPTAS for Max Clique on Disks and Unit Balls, with Marthe Bonamy, Édouard Bonnet, Pierre Charbit and Stéphan Thomassé. Reconfiguration of graphs with connectivity constraints, with Arnaud Mary. Parameterized Complexity of Independent Set in H-Free Graphs, with Edouard Bonnet, Pierre Charbit, Stéphan Thomassé and Rémi Watrigant. Distributed coloring in sparse graphs with fewer colors, with Pierre Aboulker, Marthe Bonamy and Louis Esperet. Token Jumping in minor-closed classes, with Arnaud Mary and Aline Parreau. Token Sliding on Chordal Graphs, with Marthe Bonamy. Computing maximum cliques in B_2-EPG graphs, with Marc Heinrich. On the economic efficiency of the combinatorial clock auction, with Yang Cai, Christof Hunkenschroder and Adrian Vetta. Welfare and Rationality Guarantees for the Simultaneous Multiple-Round Auction, with Yang Cai and Adrian Vetta. Coalition Games on Interaction Graphs: A Horticultural Perspective, with Zhentao Li and Adrian Vetta. A near-optimal mechanism for impartial selection, with Sergey Norin and Adrian Vetta. ]
Parameterized Complexity of the Sparsest k-Subgraph Problem in Chordal Graphs, with Marin Bougeret, Rodolphe Giroudeau and Rémi Watrigant. ]
Adjacent vertex-distinguishing edge coloring of graphs, with Marthe Bonamy and Hervé Hocquard. Recoloring bounded treewidth graphs, with Marthe Bonamy. ]
Parameterized Domination in Circle Graphs, with Daniel Gonçalves, George Mertzios, Christophe Paul, Ignasi Sau and Stéphan Thomassé.]
Multicut is FPT, with Jean Daligault, Stéphan Thomassé.]
Equivalence and Inclusion Problem for Strongly Unambiguous Büchi Automata, with Christof Löding.
]
A Polynomial Kernel for Multicut in Trees, with Jean Daligault, Stéphan Thomassé, Anders Yeo. ]
The distance between Matchings, with Tatsuhiko Hatanaka, Takehiro Ito and Moritz Mühlenthaler, submitted.
Frozen (Delta+1)-colourings of bounded degree graphs, with Marthe Bonamy and Guillem Perarnau, submitted.
On the chromatic number of wheel-free graphs with no large bipartite graphs, with Stéphan Thomassé, submitted.
Shapley value on matching games for trees, submitted.
Reconfiguration of independent sets in cographs, with Marthe Bonamy, submitted.
Hitting Sets: VC-dimension and Multicut. Le problème de l'équivalence pour les automates de Büchi fortement non ambigüs. ):
Recoloring, from statistical physics to combinatorics, One day Discrete Structure Meeting, ENS Lyon, June, 15th, 2018.
Exact distance coloring in trees, ANR DISTANCIA, Marseille, April, 11th, 2018.
Token Sliding on Chordal Graphs, BIRS Workshop, Banff, Canada, January 2017.
Discrete Maths and Optimization Seminar, McGill, September, 29th, 2014, Clique, stable sets and chromatic number.
Clermont-Ferrand, March, 28th, 2013, Hitting sets and VC-dimension.