Benjamin Lévêque

Chargé de recherche at CNRS with the Algorithms for Graphs and Combinatorics group of the LIRMM. Leader of the ANR Project Embedded Graphs and their Oriented Structures. benjamin.leveque@lirmm.fr http://www.lirmm.fr/~leveque Tel : +33 4 67 41 86 09 Office E3.22 Université Montpellier 2 LIRMM - UMR 5506 - CC 477 161 rue Ada 34095 Montpellier Cedex 5 France

Publications

• M. Bonamy, B. Lévêque, A. Pinlou, Graphs with maximum degree D at least 17 and maximum average degree less than 3 are list 2-distance (D+2)-colorable, manuscript (2012) arXiv:1301.7090. (pdf)
• D. Gonçalves, B. Lévêque, Toroidal maps : Schnyder woods, orthogonal surfaces and straight-line representations, manuscript (2012) arXiv:1202.0911. (pdf)
• P. Heggernes, P. van 't Hof, B. Lévêque, C. Paul, Contracting Chordal Graphs and Bipartite Graphs to Paths and Trees, Discrete Applied Mathematics (2012) to appear.
• P. Heggernes, P. van 't Hof, B. Lévêque, D. Lokshtanov, C. Paul, Contracting graphs to paths and trees, Algorithmica (2012) DOI:10.1007/s00453-012-9670-2. (pdf)
• B. Lévêque, F. Maffray, N. Trotignon On graphs with no induced subdivision of K4, Journal of Combinatorial Theory B 102 (2012) 924–947. (pdf)
• D. Gonçalves, B. Lévêque, A. Pinlou, Triangle contact representations and duality, Discrete and Computational Geometry 48 (2012) 239-254. (pdf)
• K. Cameron, B. Lévêque, F. Maffray, Coloring vertices of a graph or finding a Meyniel obstruction, Theoretical Computer Science 428 (2012) 10-17. (pdf)
• B. Lévêque, D. de Werra, Graph transformations preserving the stability number, Discrete Applied Mathematics 160 (2012) 2752–2759. (pdf)
• K. Cameron, C. Hoàng, B. Lévêque, Characterizing directed path graphs by forbidden asteroids, Journal of Graph Theory 68 (2011) 103-112. (pdf)
• B. Lévêque, F. Maffray, B. Reed, N. Trotignon, Coloring Artemis graphs, Theoretical Computer Science 410 (2009) 2234-2240. (pdf)
• B. Lévêque, D. Lin, F. Maffray, N. Trotignon, Detecting induced subgraphs, Discrete Applied Mathematics 157 (2009) 3540-3551. (pdf)
• B. Lévêque, F. Maffray, M. Preissmann, Characterizing path graphs by forbidden induced subgraphs, Journal of Graph Theory 62 (2009) 369-384. (pdf)
• Y. Frein, B. Lévêque, A. Sebö, Generating all sets with bounded unions, Combinatorics, Probability and Computing 17 (2008) 641-660. (pdf)
• B. Lévêque, F. Maffray, Coloring bull-free perfectly contractile graphs, SIAM Journal on Discrete Mathematics 21 (2008) 999-1018. (pdf)
• J.-C. Bermond, D. Coudert, B. Lévêque, Approximations for All-to-All Uniform Traffic Grooming on Unidirectional Ring, Journal of Interconnection Networks 9 (2008) 471-486. (pdf)
• V. Jost, B. Lévêque, F. Maffray, Precoloring extension of co-Meyniel graphs, Graphs and Combinatorics 23 (2007) 291-301. (pdf)
  

   

• P. Heggernes, P. van 't Hof, B. Lévêque, D. Lokshtanov, C. Paul, Contracting graphs to paths and trees, IPEC'11, Lecture Notes in Computer Science 7112 (2012) 55–66. (pdf)
• M. Bonamy, B. Lévêque, A. Pinlou, 2-distance coloring of sparse graphs, EUROCOMB'11, Electronic Notes in Discrete Mathematics 38 (2011) 155-160. (pdf)
• P. Heggernes, P. van 't Hof, B. Lévêque, C. Paul, Contracting chordal graphs and bipartite graphs to paths and trees, LAGOS'11, Electronic Notes in Discrete Mathematics 37 (2011) 87-92. (pdf)
• D. Gonçalves, B. Lévêque, A. Pinlou, Triangle contact representations and duality, GD'10, Lecture Notes in Computer Science 6502 (2011) 262-273. (pdf)
• S. Chaplick, M. Gutierrez, B. Lévêque, S. B. Tondato, From path graphs to directed path graphs, WG'10, Lecture Notes in Computer Science 6410 (2010) 256-265. (pdf)
• B. Lévêque, D. de Werra, Graph transformations preserving the stability number, LAGOS'09, Electronic Notes in Discrete Mathematics 35 (2009) 3-8. (pdf)
• K. Cameron, C. Hoàng, B. Lévêque, Asteroids in rooted and directed path graphs, AGT'09, Electronic Notes in Discrete Mathematics 32 (2009) 67-74. (pdf)
• B. Lévêque, D. Lin, F. Maffray, N. Trotignon, Detecting induced subgraphs, EUROCOMB'07, Electronic Notes in Discrete Mathematics 29 (2007) 207-211. (pdf)
• Y. Frein, B. Lévêque, A. Sebö, Optimizing diversity, EUROCOMB'07, Electronic Notes in Discrete Mathematics 29 (2007) 73-77. (pdf)
• B. Lévêque, F. Maffray, Coloring Meyniel graphs in linear time, ICGT'05, Electronic Notes in Discrete Mathematics 22 (2005) 25-28. (pdf, erratum)

PhD Thesis

Coloring graphs : structures and algorithms, PhD Thesis, Grenoble University, october 2007.(pdf)

Curriculum Vitae