Ararat Harutyunyan me

Ararat Harutyunyan

Assistant Professor (Maitre de Conference)
University of Paris-Dauphine.



Curriculum Vitae.

2017 Sept. -:   Assistant Professor, LAMSADE, University of Paris-Dauphine.

2015 Sept. - 2017 Sept.:   Research Fellow, ESP, Mathematical Institute of Toulouse.

2014 Sept. - 2015 Sept.:   Research Fellow, LIP, ENS de Lyon.

2013 Sept. - 2014 Sept.:   Research Fellow, Mathematical Institute, University of Oxford.

2012 Oct. - 2013 Sept.:   Digiteo Postdoctoral researcher, Laboratoire de Recherche en Informatique (LRI), Universite Paris-Sud.

2011 Sept. - 2012 June:   Postdoctoral researcher and instructor, Simon Fraser University.

2008 Sept. - 2011 June:   Ph.D. in Mathematics, Simon Fraser University.
Supervisor:   Bojan Mohar.
Thesis Title:   Brooks-type Theorems for Coloring of Digraphs.

2006 Sept. - 2008 Aug.:   MSc. in Mathematics, McGill University.
Supervisors:   Jacques Verstraete and Dmitry Jakobson.
Thesis Title:   Probabilistic Methods and Domination Related Problems in Graphs.

2003 Sept. - 2006 Aug.:   BSc Honours in Mathematics, McGill University.


Research Interests

My research interests are in graph theory. In particular, I am interested in structural graph theory, random graphs,
probabilistic methods and combinatorial and randomized graph algorithms.


  1. A. Harutyunyan, T.-N. Le, A. Newman, S. Thomassé, Domination and fractional domination in digraphs , submitted to Electronic Journal of Combinatorics.
  2. A. Harutyunyan, T.-N. Le, A. Newman, S. Thomassé, Coloring dense digraphs , submitted to Combinatorica.
  3. N. Bousquet, L. Esperet, A. Harutyunyan, R. de Joannis de Verclos, Exact distance coloring in trees. , submitted to Combinatorics, Probability and Computing .
  4. A. Harutyunyan, T.-N. Le, S. Thomassé, H. Wu, Coloring tournaments: from local to global , submitted to Journal of Combinatorial Theory (Ser. B) .
  5. A. Harutyunyan, L. Pastor, S. Thomassé Disproving the normal graphs conjecture , submitted to Journal of Combinatorial Theory (Ser. B) .
  6. J. Bensmail, A. Harutyunyan, N.-K. Le, B. Li, N. Lichiardopol, Disjoint cycles of different lengths in graphs and digraphs, accepted in Electronic Journal of Combinatorics .
  7. J. Bensmail, A. Harutyunyan, N.-K. Le, List coloring digraphs , Journal of Graph Theory, accepted.
  8. J. Bensmail, A. Harutyunyan, T.-N. Le, S. Thomassé, Edge-partitioning a graph into paths: beyond the Barát-Thomassen conjecture , accepted Combinatorica .
  9. A. Harutyunyan, P. Horn, J. Verstraete, Independent dominating sets in graphs of girth five ,Combinatorics, Probability and Computing, accepted.
  10. F. Foucaud, A. Harutyunyan, P. Hell, S. Legay, R. Naserasr, Y. Manoussakis, The complexity of tropical graph homomorphisms , Discrete Applied Mathematics 229: 64-81 (2017) .
  11. J. Bensmail, A. Harutyunyan, T.-N. Le, M. Merker, S. Thomassé, A proof of the Barát-Thomassen conjecture , Journal of Combinatorial Theory, Ser. B 124, pp. 39 – 55, 2017.
  12. A. Harutyunyan, B. Mohar, Planar digraphs of digirth five are 2-colorable , Journal of Graph Theory 84(4): 408 - 427, 2017 .
  13. J-A. Angles d'Auriac, N. Cohen, A. El Maftouhi, A. Harutyunyan, S. Legay, Y. Manoussakis, Connected tropical subgraphs in vertex-colored graphs , Discrete Mathematics and Theoretical Computer Science 17:3, pp. 327-348, 2016 .
  14. A. Harutyunyan, R. Naserasr, M. Petrusevski, R. Skrekovski, Q. Sun, Mapping planar graphs into the Coxeter graph, Discrete Mathematics 339, pp. 839 - 849, 2016 .
  15. A. Harutyunyan, S. Legay, Linear time algorithms for weighted offensive and powerful alliances in trees , Theoretical Computer Science 582, pp. 17 - 26, 2015 .
  16. A. El Maftouhi, A. Harutyunyan, Y. Manoussakis, Weak balance in random signed graphs , Internet Mathematics 11(2), pp. 143-154, 2015.
  17. J. Bensmail, A. Harutyunyan, H. Hocquard, P. Valicov, Strong-edge coloring of planar graphs , Discrete Applied Mathematics 179, pp. 229-234, 2014.
  18. A. Harutyunyan, Global Offensive Alliances in Graphs and Random Graphs. , Discrete Applied Mathematics 164, pp. 522-526, 2014.
  19. A. Harutyunyan, Some bounds on global alliances in trees , Discrete Applied Mathematics 161, pp. 1739-1746, 2013 .
  20. A. Harutyunyan, P.M. Kayll, B. Mohar, L. Rafferty, Uniquely D-colorable digraphs with large girth , The Canadian Journal of Mathematics 64, 1310-1328, 2012.
  21. A. Harutyunyan, B. Mohar, Planar graphs have exponentially many 3-arboricities , SIAM Journal on Discrete Mathematics 26(3), pp. 1269-1280, 2012.
  22. A. Harutyunyan, B. Mohar, Two results on the digraph chromatic number , Discrete Mathematics 312(10), pp. 1823-1826, 2012 .
  23. A. Harutyunyan, B. Mohar, Gallai's Theorem for List Coloring of Digraphs , SIAM Journal on Discrete Mathematics 25(1), pp. 170-180, 2011.
  24. A. Harutyunyan, B. Mohar, Strengthened Brooks Theorem for digraphs of girth three , The Electronic Journal of Combinatorics 18 (2011), #P195.
  25. A. Harutyunyan, A Fast Algorithm for Powerful Alliances in Trees , 4th International Conference on Combinatorial Optimization and Applications ( COCOA 2010 ), Kailua-Kona, HI, USA,
    LNCS 6508 (1) 2010: 31-40.
  26. A. Harutyunyan, Global Offensive Alliances in Graphs via Degree Sequences , VI Latin-American Conference Algorithms, Graphs and Optimization Symposium ( LAGOS 2011 ).
  27. A. Harutyunyan, Some Bounds on Alliances in Trees, 9th Cologne Twente Workshop on Graphs and Combinatorial Optimization ( CTW 2010 ), Cologne, Germany, 2010: 83-86.

Useful homepages

Bojan Mohar, Stéphan Thomassé , Jacques Verstraete, Pavol Hell Colin McDiarmid, Alex Scott, Jacob Fox

Conferences I will attend in 2017-2018

The 1st Southwestern German Workshop on Graph Theory , Karlsruhe, Germany, August 27-31, 2018.

ICGT 2018 , Lyon, France, July 9-13, 2018.

Building bridges II (70th anniversary of Lovasz) , Budapest, Hungary, July 2-6, 2018.

JGA 2017 , Bordeaux, France, November 15-17, 2017.

CanaDAM , Toronto, Canada, June 12-16, 2017.


In addition to the following courses taught as a lecturer, I have also served as a teaching assistant for many different courses such as Graph Theory, Algebra, Linear Optimisation.


Graph Theory (First year students), Winter 2016, Supaero-Isae, Toulouse.

MACM 201 (Discrete Mathematics II), Winter 2012, SFU. Teaching Evaluation .

MATH 150 (Calculus I), Fall 2011, SFU. Teaching Evaluation .

Some slides of talks

A proof of the Barat-Thomassen Conjecture, 3rd Bordeaux Graph Workshop, Bordeaux, France, November 7-10, 2016 Slides .

Colorings in planar graphs and digraphs, SIAM conference on Discrete Mathematics, Minneapolis, USA, June 16-19, 2014 Slides .

Independent dominating sets via semi-random method, Slides .

Sparsity and homomorphisms of digraphs, Slides .


Erdos number: 2 (through Pavol Hell )