Ararat Harutyunyan me

Ararat Harutyunyan

LabEx CIMI Research Fellow
Mathematical Institute,
University of Toulouse III.


Welcome! I am currently a research fellow (chercheur-visiteur) at the Mathematical Institute, University of Toulouse III (Paul Sabatier), in the research team ESP (Probability and Statistics).


I am an organizer of the Probability seminar .


Curriculum Vitae.

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 and discharging methods and combinatorial and randomized graph algorithms.


  1. A. Harutyunyan, T.-N. Le, A. Newman, S. Thomassé, Coloring dense digraphs .
  2. N. Bousquet, L. Esperet, A. Harutyunyan, R. de Joannis de Verclos, Exact distance coloring in trees. , submitted to Combinatorics, Probability and Computing .
  3. A. Harutyunyan, T.-N. Le, S. Thomassé, H. Wu, Coloring tournaments: from local to global , submitted to Journal of Combinatorial Theory (Ser. B) .
  4. J. Bensmail, A. Harutyunyan, N.-K. Le, B. Li, N. Lichiardopol, Disjoint cycles of different lengths in graphs and digraphs, submitted to Electronic Journal of Combinatorics .
  5. J. Bensmail, A. Harutyunyan, N.-K. Le, List coloring digraphs , submitted to Journal of Graph Theory.
  6. J. Bensmail, A. Harutyunyan, T.-N. Le, S. Thomassé, Edge-partitioning a graph into paths: beyond the Barát-Thomassen conjecture , submitted to Combinatorica .
  7. A. Harutyunyan, L. Pastor, S. Thomassé Disproving the normal graphs conjecture , submitted to Journal of Combinatorial Theory (Ser. B) .
  8. F. Foucaud, A. Harutyunyan, P. Hell, S. Legay, R. Naserasr, Y. Manoussakis, The complexity of tropical graph homomorphisms , Discrete Applied Mathematics , to appear.
  9. A. Harutyunyan, P. Horn, J. Verstraete, Independent dominating sets in graphs of girth five ,Combinatorics, Probability and Computing, accepted.
  10. 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.
  11. A. Harutyunyan, B. Mohar, Planar digraphs of digirth five are 2-colorable , Journal of Graph Theory 84(4): 408 - 427, 2017 .
  12. 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 .
  13. A. Harutyunyan, R. Naserasr, M. Petrusevski, R. Skrekovski, Q. Sun, Mapping planar graphs into the Coxeter graph, Discrete Mathematics 339, pp. 839 - 849, 2016 .
  14. A. Harutyunyan, S. Legay, Linear time algorithms for weighted offensive and powerful alliances in trees , Theoretical Computer Science 582, pp. 17 - 26, 2015 .
  15. A. El Maftouhi, A. Harutyunyan, Y. Manoussakis, Weak balance in random signed graphs , Internet Mathematics 11(2), pp. 143-154, 2015.
  16. J. Bensmail, A. Harutyunyan, H. Hocquard, P. Valicov, Strong-edge coloring of planar graphs , Discrete Applied Mathematics 179, pp. 229-234, 2014.
  17. A. Harutyunyan, Global Offensive Alliances in Graphs and Random Graphs. , Discrete Applied Mathematics 164, pp. 522-526, 2014.
  18. A. Harutyunyan, Some bounds on global alliances in trees , Discrete Applied Mathematics 161, pp. 1739-1746, 2013 .
  19. 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.
  20. A. Harutyunyan, B. Mohar, Planar graphs have exponentially many 3-arboricities , SIAM Journal on Discrete Mathematics 26(3), pp. 1269-1280, 2012.
  21. A. Harutyunyan, B. Mohar, Two results on the digraph chromatic number , Discrete Mathematics 312(10), pp. 1823-1826, 2012 .
  22. A. Harutyunyan, B. Mohar, Gallai's Theorem for List Coloring of Digraphs , SIAM Journal on Discrete Mathematics 25(1), pp. 170-180, 2011.
  23. A. Harutyunyan, B. Mohar, Strengthened Brooks Theorem for digraphs of girth three , The Electronic Journal of Combinatorics 18 (2011), #P195.
  24. 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.
  25. A. Harutyunyan, Global Offensive Alliances in Graphs via Degree Sequences , VI Latin-American Conference Algorithms, Graphs and Optimization Symposium ( LAGOS 2011 ).
  26. 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 2016-2017

Advanced Mathematics for Network Analysis , Luchon, France, May 1-4, 2016.

SIAM Conference on Discrete Mathematics , Atlanta, USA, June 6-10, 2016.

Bordeaux Graph Workshop , Bordeaux, France, November 7-10, 2016.

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 )