CNRS researcher - Benjamin Lévêque

Benjamin Lévêque Laboratoire G-SCOP 46 Avenue Félix Viallet 38031 GRENOBLE CEDEX 1 France benjamin.leveque@grenoble-inp.fr http://pagesperso.g-scop.grenoble-inp.fr/~levequeb/ Tel : +33 4 76 57 49 65 Office H325 Chargé de recherche at CNRS with the Combinatorial Optimization group of the G-SCOP.

PhD and habilitation

• Generalization of Schnyder woods to orientable surfaces and applications (pdf)
  B. Lévêque, Habilitation manuscript, 19/10/2016.

• Coloration de graphes : structures et algorithmes (pdf)
  B. Lévêque, PhD manuscript, 15/10/2007.

Articles

• Locating Dominating Sets in local tournaments (pdf)
  T. Bellitto, C. Brosse, B. Lévêque, A. Parreau, manuscript arXiv:2109.03102.

• Scaling limits for random triangulations on the torus (pdf)
  V. Beffara, C.B. Huynh, B. Lévêque, manuscript, arXiv:1905.01873.

• Local certification of graphs on surfaces (pdf)
  L. Esperet, B. Lévêque, Theoretical Computer Science 909 (2022) 68-75.

• A bijection for essentially 3-connected toroidal maps (pdf)
  N. Bonichon, É. Fusy, B. Lévêque, European Journal of Combinatorics 95 (2021) 103290.

• Orientations and bijections for toroidal maps with prescribed face-degrees and essential girth (pdf)
  É. Fusy, B. Lévêque, Journal of Combinatorial Theory, Series A 175 (2020) 105270.

• Homothetic triangle representations of planar graphs (pdf)
  D. Gonçalves, B. Lévêque, A. Pinlou, Journal of Graph Algorithms and Applications 23 (2019) 745-753.

• A bijection for essentially 4-connected toroidal triangulations (pdf)
  N. Bonichon, B. Lévêque, The Electronic Journal of Combinatorics 26 (2019) P1.13.

• On the structure of Schnyder woods on orientable surfaces (pdf)
  D. Gonçalves, K. Knauer, B. Lévêque, Journal of Computational Geometry 10 (2019) 127-164.

• Encoding toroidal triangulations (pdf)
  V. Despré, D. Gonçalves, B. Lévêque, Discrete and Computational Geometry 57 (2017) 507-544.

• Planar graphs with Delta>=7 and no triangle adjacent to a C4 are minimally edge- and totally-choosable (pdf)
  M. Bonamy, B. Lévêque, A. Pinlou, Discrete Mathematics & Theoretical Computer Science 17 (2016) 131-146.

• Asteroidal quadruples in non rooted path graphs (pdf)
  M. Gutierrez, B. Lévêque, S. B. Tondato, Discussiones Mathematicae Graph Theory 35 (2015) 603-614.

• Toroidal maps : Schnyder woods, orthogonal surfaces and straight-line representations (pdf)
  D. Gonçalves, B. Lévêque, Discrete and Computational Geometry 51 (2014) 67-131.

• List coloring the square of sparse graphs with large degree (pdf)
  M. Bonamy, B. Lévêque, A. Pinlou, European Journal of Combinatorics 41 (2014) 128-137.

• Graphs with maximum degree D at least 17 and maximum average degree less than 3 are list 2-distance (D+2)-colorable (pdf)
  M. Bonamy, B. Lévêque, A. Pinlou, Discrete Mathematics 317 (2014) 19-32.

• 2-distance coloring of sparse graphs (pdf)
  M. Bonamy, B. Lévêque, A. Pinlou, Journal of Graph Theory 77 (2014) 190–218.

• Contracting Chordal Graphs and Bipartite Graphs to Paths and Trees (pdf)
  P. Heggernes, P. van 't Hof, B. Lévêque, C. Paul, Discrete Applied Mathematics 164 (2014) 444–449.

• Contracting graphs to paths and trees (pdf)
  P. Heggernes, P. van 't Hof, B. Lévêque, D. Lokshtanov, C. Paul, Algorithmica 68 (2014) 109-132.

• On graphs with no induced subdivision of K4 (pdf)
  B. Lévêque, F. Maffray, N. Trotignon, Journal of Combinatorial Theory, Series B 102 (2012) 924–947.

• Triangle contact representations and duality (pdf)
  D. Gonçalves, B. Lévêque, A. Pinlou, Discrete and Computational Geometry 48 (2012) 239-254.

• Coloring vertices of a graph or finding a Meyniel obstruction (pdf)
  K. Cameron, B. Lévêque, F. Maffray, Theoretical Computer Science 428 (2012) 10-17.

• Graph transformations preserving the stability number (pdf)
  B. Lévêque, D. de Werra, Discrete Applied Mathematics 160 (2012) 2752–2759.

• Characterizing directed path graphs by forbidden asteroids (pdf)
  K. Cameron, C. Hoàng, B. Lévêque, Journal of Graph Theory 68 (2011) 103-112.

• Coloring Artemis graphs (pdf)
  B. Lévêque, F. Maffray, B. Reed, N. Trotignon, Theoretical Computer Science 410 (2009) 2234-2240.

• Detecting induced subgraphs (pdf)
  B. Lévêque, D. Lin, F. Maffray, N. Trotignon, Discrete Applied Mathematics 157 (2009) 3540-3551.

• Characterizing path graphs by forbidden induced subgraphs (pdf)
  B. Lévêque, F. Maffray, M. Preissmann, Journal of Graph Theory 62 (2009) 369-384.

• Generating all sets with bounded unions (pdf)
  Y. Frein, B. Lévêque, A. Sebö, Combinatorics, Probability and Computing 17 (2008) 641-660.

• Coloring bull-free perfectly contractile graphs (pdf)
  B. Lévêque, F. Maffray, SIAM Journal on Discrete Mathematics 21 (2008) 999-1018.

• Approximations for All-to-All Uniform Traffic Grooming on Unidirectional Ring (pdf)
  J.-C. Bermond, D. Coudert, B. Lévêque, Journal of Interconnection Networks 9 (2008) 471-486.

• Precoloring extension of co-Meyniel graphs (pdf)
  V. Jost, B. Lévêque, F. Maffray, Graphs and Combinatorics 23 (2007) 291-301.

Conferences articles

• Contracting graphs to paths and trees (pdf)
  P. Heggernes, P. van 't Hof, B. Lévêque, D. Lokshtanov, C. Paul, IPEC'11, Lecture Notes in Computer Science 7112 (2012) 55–66.

• 2-distance coloring of sparse graphs (pdf)
  M. Bonamy, B. Lévêque, A. Pinlou, EUROCOMB'11, Electronic Notes in Discrete Mathematics 38 (2011) 155-160.

• Contracting chordal graphs and bipartite graphs to paths and trees (pdf)
  P. Heggernes, P. van 't Hof, B. Lévêque, C. Paul, LAGOS'11, Electronic Notes in Discrete Mathematics 37 (2011) 87-92.

• Triangle contact representations and duality (pdf)
  D. Gonçalves, B. Lévêque, A. Pinlou, GD'10, Lecture Notes in Computer Science 6502 (2011) 262-273.

• From path graphs to directed path graphs (pdf)
  S. Chaplick, M. Gutierrez, B. Lévêque, S. B. Tondato, WG'10, Lecture Notes in Computer Science 6410 (2010) 256-265.

• Graph transformations preserving the stability number (pdf)
  B. Lévêque, D. de Werra, LAGOS'09, Electronic Notes in Discrete Mathematics 35 (2009) 3-8.

• Asteroids in rooted and directed path graphs (pdf)
  K. Cameron, C. Hoàng, B. Lévêque, AGT'09, Electronic Notes in Discrete Mathematics 32 (2009) 67-74.

• Detecting induced subgraphs (pdf)
  B. Lévêque, D. Lin, F. Maffray, N. Trotignon, EUROCOMB'07, Electronic Notes in Discrete Mathematics 29 (2007) 207-211.

• Optimizing diversity (pdf)
  Y. Frein, B. Lévêque, A. Sebö, EUROCOMB'07, Electronic Notes in Discrete Mathematics 29 (2007) 73-77.

• Coloring Meyniel graphs in linear time (pdf, erratum)
  B. Lévêque, F. Maffray, ICGT'05, Electronic Notes in Discrete Mathematics 22 (2005) 25-28.