Nicolas Bousquet

ATER at Ecole Centrale de Lyon, France.

Bâtiment NR
36 avenue Guy de Collongue
69134 Ecully, FRANCE.


I am now an ATER (temporary assistant professor position) in Ecole Centrale de Lyon. I am a member of the LIRIS laboratory where I worked in the GOAL ( Graphes, AlgOrithmes et AppLications) team. Formerly, I was a postodoctoral fellow at the Department of Mathematics and Statistics at McGill University where I worked with Adrian Vetta. I was partially funded by the GERAD (Groupe d'études et de recherche en analyse des décisions).
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). The topic 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 (without preference order): Here, you can find a short CV.


In order to access to the paper, click on the pdf icon.

International journals

  1. Fast recoloring of sparse graphs, with Guillem Perarnau, European Journal of Combinatorics, 52 (2016), pp 1-11.
  2. The Erdos-Hajnal Conjecture for long holes and antiholes, with Marthe Bonamy and Stéphan Thomassé, to appear in SIAM Journal on Discrete Mathematics.
  3. Identifying codes in hereditary classes of graphs and VC-dimension, with Aurélie Lagoutte, Zhentao Li, Aline Parreau and Stéphan Thomassé, SIAM Journal on Discrete Mathematics 29-4 (2015), pp. 2047-2064.
  4. VC-dimension and Erdös-Pósa property of graphs, with Stéphan Thomassé, Discrete Mathematics, 338-12, pp. 2302-2317 (2015).
  5. The Erdos-Hajnal Conjecture for Paths and Antipaths, with Aurélie Lagoutte and Stéphan Thomassé, Journal of Comb. Theory Series B, 113 (2015), pp. 261-264.
  6. Excluding cycles with a fixed number of chords, with Pierre Aboulker, Discrete Applied Mathematics 180 (2015) 11-24. [Bibtex ]
  7. Clique versus independent set, with Aurélie Lagoutte and Stéphan Thomassé, European Journal of Combinatorics 40 (2014), 73-92. [Bibtex ]
  8. Brooks' theorem on powers of graphs, with Marthe Bonamy, Discrete Mathematics 325 (2014), 12-16. [Bibtex ]
  9. Parameterized Domination in Circle Graphs with Daniel Gonçalves, George Mertzios, Christophe Paul, Ignasi Sau and Stéphan Thomassé, Theory of Computing Systems 54(1):45-72, 2014. [Bibtex ]
  10. Scott's induced subdivision conjecture for maximal triangle-free graphs with Stéphan Thomassé, Combinatorics, Probability and Computing, 21 (2012) 512-514. [Bibtex ]

International Conferences

  1. On the economic efficiency of the combinatorial clock auction, with Yang Cai, Christof Hunkenschroder and Adrian Vetta, SODA'16, pp. 1407-1423.
  2. Welfare and Rationality Guarantees for the Simultaneous Multiple-Round Auction, with Yang Cai and Adrian Vetta, WINE'15 , pp.2 16-229.
  3. Coalition Games on Interaction Graphs: A Horticultural Perspective, with Zhentao Li and Adrian Vetta, EC'15, pp. 95-112.
  4. A near-optimal mechanism for impartial selection, with Sergey Norin and Adrian Vetta, WINE'14, pp. 133-146. [Bibtex ]
  5. Parameterized Complexity of the Sparsest k-Subgraph Problem in Chordal Graphs, with Marin Bougeret, Rodolphe Giroudeau and Rémi Watrigant, SOFSEM'14, Springer Lecture Notes in Computer Science 8327, pp. 150-161. [Bibtex ]
  6. Adjacent vertex-distinguishing edge coloring of graphs, with Marthe Bonamy and Hervé Hocquard, EuroComb'13, CRM Series Volume 16, 2013, pp 313-318 .
  7. Recoloring bounded treewidth graphs, with Marthe Bonamy, LAGOS'13, Electronic Notes in Discrete Math. 44: 257-262, 2013. [Bibtex ]
  8. Parameterized Domination in Circle Graphs, with Daniel Gonçalves, George Mertzios, Christophe Paul, Ignasi Sau and Stéphan Thomassé, WG'12, volume 7551 of Lecture Notes in Computer Science (2012) 308-319. [Bibtex ]
  9. Multicut is FPT, with Jean Daligault, Stéphan Thomassé, STOC'11, Proceedings of the 43rd annual ACM symposium on Theory of computing (2011), 459-468. [Bibtex ]
  10. Equivalence and Inclusion Problem for Strongly Unambiguous Büchi Automata, with Christof Löding, LATA 2010 , volume 6031 of Lecture Notes in Computer Science, (2010) 118-129. [Bibtex ]
  11. A Polynomial Kernel for Multicut in Trees, with Jean Daligault, Stéphan Thomassé, Anders Yeo, STACS'09, (2009) 183-194. [Bibtex ]


  1. Sampling (d + 1)-colorings of d-regular graphs, with Guillem Perarnau, submitted.
  2. A Vizing-like theorem for union vertex-distinguishing edge coloring, with Antoine Dailly, Eric Duchêne, Hamamache Kheddouci et Aline Parreau, submitted.
  3. On a conjecture of Mohar concerning Kempe equivalence, with Marthe Bonamy, Carl Feghali and Matthew Johnson, submitted .
  4. On the chromatic number of wheel-free graphs with no large bipartite graphs, with Stéphan Thomassé, submitted.
  5. Shapley value on matching games for trees, submitted.
  6. Parameterized Complexity of the Sparsest k-Subgraph Problem in Chordal Graphs (journal version), with Marin Bougeret, Rodolphe Giroudeau and Rémi Watrigant, submitted.
  7. Reconfiguration of independent sets in cographs, with Marthe Bonamy, submitted.
  8. Multicut is FPT (journal version), with Jean Daligault and Stéphan Thomassé, submitted.
  9. Recoloring graphs via tree-decompositions, with Marthe Bonamy, submitted.
  10. Colourful paths for 3-chromatic graphs, with Stéphane Bessy, submitted.




You can find the details and the slides of all my talks there. In this page, I just mentionned a couple of my more recent talks (to see the slides, click on the picture ):

You may have seen me there:

Here the next few events I'll participate and the last places you might have seen me. For a complete list, see here.