## Alexandre Pinlou - LIRMM, Polytech, University of Montpellier

I am full professor in Computer Science at Polytech Montpellier, engineering school of the University of Montpellier. From September 2008 to August 2017, I was associate professor (« maître de conférences ») at the MIAp department of the University Paul-Valéry, Montpellier 3.

I am head of the Transversal Computer Science Department (« Pôle Informatique Transversal ») of Polytech Montpellier. I teach information technology and network tools, databases, algorithms, computer programming, and graph theory.

I am member of the Algorithms on Graphs & Combinatorics group of the LIRMM. Previously, I was member of the Graphs & Applications group of the LaBRI.

My research topics are mainly focused on homomorphisms and graph colorings, vertex partitions, discharging methods, entropy compression method, and recently on combinatorics on words.

I currenlty co-supervise two Ph.D. candidates: Fabien Jacques who is working on homomorphisms of signed graphs, and Hoang La who is working on 2-distance colorings.

I am deputy head of the Computer Science Department of the LIRMM since January 2020.

## Curriculum Vitæ

• 41 years old
• 2 children

### Education

 Dec. 2014 « Habilitation à diriger des recherches » in Computer Science, University Montpellier 2 Oct. 2006 Ph.D. in Computer Science, University Bordeaux 1 June 2003 Graduated in Computer Science, University Bordeaux 1

### Work Experience

 2017 - ... Full professor at Polytech Montpellier, University of Montpellier 2012 - 2013 Recipient of a full-time CNRS teaching leave 2008 - 2017 Associate professor at MIAp department, university Paul-Valéry, Montpellier 3 2007 - 2008 Lecturer in the MIAp department of the university Paul-Valéry, Montpellier 3 2006 - 2007 Lecturer in the computer science department of the IUT Bordeaux 1 2003 - 2006 Ph.D. student in the LaBRI / Lecturer in the computer science department of the IUT Bordeaux 1

 2020 - ... Deputy head of the Computer Science Department of the LIRMM. 2017 - ... Head of the Transversal Computer Science Department (« Pôle transversal informatique ») at Polytech Montpellier 2017 - ... Member of the « Comité NUMérique pour la Formation » (CNUMF) of the University of Montpellier 2016 - 2019 Elected member of the Council of the doctoral school I2S 2016 - ... Coordinator of the « Computer ressources committee » of the LIRMM 2015 - 2017 Member of the Finance committee of University Paul-Valéry Montpellier 3 2015 - 2017 Elected member of the Laboratory Council of the LIRMM (second mandate) 2014 - 2016 Deputy head of the Computer Science Department of the LIRMM. 2012 - 2016 Co-head of the GT Graphes, group of the GDR Informatique Mathématique of CNRS. May 2012 Member of the recruitment committee (computer science) of university Montpellier 3 2010 - 2014 Elected member of the Laboratory Council of the LIRMM (first mandate) 2009 - 2016 Webmaster of the GT Graphes, group of the GDR Informatique Mathématique of CNRS. 2007 - 2012 Co-manager of the weekly seminar of AlGCo group. 2004 - 2005 Member of the administrative council of AFoDIB

## Research Activities

My research topics are mainly focused on homomorphisms and graph colorings, vertex partitions, discharging methods, entropy compression method, and recently on combinatorics on words.

• Homomorphisms and graph colorings
I am interested in oriented and signed colorings of graphs. The notion of homomorphism is closely related to the notion of graph coloring, and therefore a part of my researches consist to prove that, for a given graph class $C$, every graph of $C$ admits a homomorphism to a given target graph.
• Discharging method
The discharging method is one of the famous methods used to prove that a planar graph or a graph with bounded maximum average degree admits a given coloring. I am interested in this notion and its improved version, that is the global discharging method where the weight can travel arbitrarily far away from the source.
• Vertex partitions of planar graphs
The Four Color Theorem says that the vertices of a planar graph can be partitioned into four empty graphs. I have particular interest in the following question: What happens if we want to partition the vertices into classes such as paths, forests, graphs with maximum degree at most $k$, graphs with order at most $k$ ? It is for example known that the vertices of a planar graph can be partitioned into three linear forests, or into a forest and a forest of maximum degree at most 5.
• Entropy compression method
The entropy compression method is a method derived from a breakthrough by Moser and Tardos who provide algorithmic version of the Lovász Local Lemma in quite general circumstances. This nice method seems to be applicable to colorings problems whenever the Local Lovasz Lemma is, with the benefits of providing tighter bounds.
• Combinatorics on words
I recently became interested in problems of combinatorics on words such as pattern avoidance, repetition threshold, or generalization of Thue sequences.

### Project Grants

 2020 - 2024 ANR Project DIGRAPHS (Directed graphs) 2020 - 2021 PHC Proteus Project with Ljubljana University, Slovenia (Edge-coloring of graphs) 2017 - 2021 ANR Project HOSIGRA (HOmomorphisms of SIgned GRAphs) 2014 - 2016 PHC Proteus Project with Ljubljana University, Slovenia (Coloring graphs on surfaces) 2012 - 2015 ANR Project EGOS (Embedded Graphs and their Oriented Structures) 2012 - 2014 PEPS Project HOGRASI (Homomorphism of signed graphs) 2009 - 2012 ANR Project GRATOS (GRAphs through TOpological Structure)

### Ph.D. Students

 2019 - 2022 Fabien Jacques, Homomorphisms of signed graphs. (co-supervision with M. Montassier) 2019 - 2022 Hoang La, Hued coloring of graphs. (co-supervision with M. Montassier and P. Valicov) 2015 - 2018 François Dross, La conjecture de Albertson et Berman (1976) et ses variations. (co-supervision with M. Montassier) 2011 - 2015 Marthe Bonamy, Global discharging procedures to settle graph optimisation problems (co-supervision with B. Lévêque)

## Publications

### International journals with program committee

1. H. La, M. Montassier, A. Pinlou, P. Valicov. $r$-hued $(r+1)$-coloring of planar graphs with girth at least 8 for $r\ge 9$. European Journal of Combinatorics, 91:103219, 2021.
2. B. Lužar, M. Mockovčiaková, P. Ochem, A. Pinlou, R. Soták. On non-repetitive sequences of arithmetic progressions: the cases $k \in$ { 4,5,6,7,8 }. Discrete Applied Mathematics, 279:106-119, 2020.
3. D. Gonçalves, M. Montassier, A. Pinlou. Acyclic coloring of graphs and entropy compression method. Discrete Mathematics, 343(4):111772, 2020.
4. J. Dybizbański, P. Ochem, A. Pinlou, A. Szepietowski. Oriented cliques and colorings of graphs with low maximum degree. Discrete Mathematics, 343(5):111829, 2020.
5. D. Gonçalves, B. Lévêque, A. Pinlou. Homothetic triangle representations of planar graphs. Journal of Graph Algorithms and Applications, 23(4):745-753, 2019.
6. F. Dross, M. Montassier, A. Pinlou. A lower bound on the order of the largest induced linear forest in triangle-free planar graphs. Discrete Mathematics, 342(4):943-950, 2019.
7. F. Dross, M. Montassier, A. Pinlou. Large induced forests in planar graphs with girth 4. Discrete Applied Mathematics, 254:96-106, 2019.
8. B. Lužar, P. Ochem, A. Pinlou. On repetition thresholds of caterpillars and trees of bounded degree. Electronic Journal of Combinatorics, 25(1):1-10, 2018.
9. F. Dross, M. Montassier, A. Pinlou. Partitioning sparse graphs into an independent set and a forest of bounded degree. Electronic Journal of Combinatorics, 25(1):1-13, 2018.
10. F. Dross, M. Montassier, A. Pinlou. Partitioning a triangle-free planar graph into a forest and a forest of bounded degree. European Journal of Combinatorics, 66:81-94, 2017.
11. M. Bonamy, M. Knor, B. Lužar, A. Pinlou, R. Škrekovski. On the difference between the Szeged and Wiener index. Applied Mathematics and Computation, 312:202-213, 2017.
12. P. Ochem, A. Pinlou, S. Sen. Homomorphisms of 2-edge-colored triangle-free planar graphs. Journal of Graph Theory, 85(1):258-277, 2017.
13. F. Dross, M. Montassier, A. Pinlou. A lower bound on the order of the largest induced forest in planar graphs with high girth. Discrete Applied Mathematics, 214:99-107, 2016.
14. M. Bonamy, B. Lévêque, A. Pinlou. Planar graphs with $\Delta\geq 7$ and no triangle adjacent to a $C_4$ are minimally edge- and total-choosable. Discrete Mathematics and Theoretical Computer Science, 17(3), 2016.
15. M. Bonamy, B. Lévêque, A. Pinlou. 2-distance coloring of sparse graphs. Journal of Graph Theory, 77(3):190-218, 2014.
16. M. Bonamy, B. Lévêque, A. Pinlou. Graphs with maximum degree $\Delta \ge 17$ and maximum average degree less than 3 are list 2-distance ($\Delta + 2$)-colorable. Discrete Mathematics, 317:19-32, 2014.
17. M. Bonamy, B. Lévêque, A. Pinlou. List coloring the square of sparse graphs with large degree. European Journal of Combinatorics, 41:128-137, 2014.
18. P. Ochem, A. Pinlou. Application of entropy compression in pattern avoidance. The Electronic Journal of Combinatorics, 21(2):1-12, 2014.
19. P. Ochem, A. Pinlou. Oriented coloring of triangle-free planar graphs and 2-outerplanar graphs. Graphs and Combinatorics, 30(2):439-453, 2014.
20. D. Goncalves, A. Parreau, A. Pinlou. Locally identifying coloring in bounded expansion classes of graphs. Discrete Applied Mathematics, 161(18):2946-2951, 2013.
21. L. Esperet, M. Montassier, P. Ochem, A. Pinlou. A complexity dichotomy for the coloring of sparse graphs. Journal of Graph Theory, 73(1):85-102, 2013.
22. D. Goncalves, B. Lévêque, A. Pinlou. Triangle contact representations and duality. Discrete and Computational Geometry, 48(1):239-254, 2012.
23. D. Goncalves, F. Havet, A. Pinlou, S. Thomassé. On spanning galaxies in digraphs. Discrete Applied Mathematics, 160(6):744-754, 2012.
24. D. Goncalves, A. Pinlou, M. Rao, S. Thomassé. The Domination Number of Grids. SIAM Journal of Discrete Mathematics, 25:1443-1453, 2011.
25. A. Montejano, P. Ochem, A. Pinlou, A. Raspaud, E. Sopena. Homomorphisms of 2-edge-colored graphs. Discrete Applied Mathematics, 158(12):1365-1379, 2010.
26. L. Addario-Berry, L. Esperet, R. Kang, C. McDiarmid, A. Pinlou. Acyclic improper colourings of graphs with bounded maximum degree. Discrete Mathematics, 310(2):223 - 229, Selected paper from the 21st British Combinatorial Conference, 2010.
27. A. Pinlou. An oriented coloring of planar graphs with girth at least five. Discrete Mathematics, 309(8):2108-2118, 2009.
28. M. Montassier, P. Ochem, A. Pinlou. Strong oriented chromatic number of planar graphs without short cycles. Discrete Mathematics and Theoretical Computer Science, 10(1):1-24, 2008.
29. P. Ochem, A. Pinlou, E. Sopena. On the oriented chromatic index of oriented graphs. Journal of Graph Theory, 57(4):313-332, 2008.
30. P. Ochem, A. Pinlou. Oriented colorings of partial 2-trees. Information Processing Letters, 108:82-86, 2008.
31. A. Pinlou, E. Sopena. Oriented vertex and arc colorings of outerplanar graphs. Information Processing Letters, 100(3):97-104, 2006.
32. A. Pinlou. On oriented arc-coloring of subcubic graphs. Electronic Journal of Combinatorics, 13(1):1-13, 2006.
33. A. Pinlou, E. Sopena. The acircuitic directed star arboricity of subcubic graphs is at most four. Discrete Mathematics, 306(24):3281-3289, 2006.

### International conferences with program committee

1. F. Jacques, M. Montassier, A. Pinlou. The chromatic number and switching chromatic number of 2-edge-colored graphs of bounded degree. In 5th Bordeaux Graph Workshop, 2019.
2. H. La, M. Montassier, A. Pinlou, P. Valicov. $r$-hued coloring of planar graphs with girth at least 8. In 5th Bordeaux Graph Workshop, 2019.
3. B. Lužar, M. Mockovčiaková, P. Ochem, A. Pinlou, R. Soták. On a conjecture on k-Thue sequences. In 4th Bordeaux Graph Workshop, 2016.
4. F. Dross, M. Montassier, A. Pinlou. Partitioning sparse graphs into an independent set and a forest of bounded degree. In 4th Bordeaux Graph Workshop, 2016.
5. F. Dross, M. Montassier, A. Pinlou. Partitioning a triangle-free planar graph into a forest and a forest of bounded degree. In European Conference on Combinatorics, Graph Theory and Applications, EuroComb 2015, 49:269-275, 2015.
6. D. Gonçalves, M. Montassier, A. Pinlou. Entropy compression method applied to graph colorings. In 9th International colloquium on graph theory and combinatorics, 2014.
7. M. Bonamy, B. Lévêque, A. Pinlou. Graphs with $mad < 3$ and $\Delta \ge 17$ are list $2$-distance $(\Delta + 2)$-colorable. In 2nd Bordeaux Graph Workshop, 2012.
8. D. Goncalves, B. Lévêque, A. Pinlou. Triangle contact representations and duality. In Proceedings of the 18th international conference on Graph drawing, pages 262-273, Springer-Verlag, 2011.
9. M. Bonamy, B. Lévêque, A. Pinlou. 2-distance coloring of sparse graphs. In European Conference on Combinatorics, Graph Theory and Applications, EuroComb 2011, 38:155-160, 2011.
10. P. Ochem, A. Pinlou. Oriented Coloring of Triangle-Free Planar Graphs and 2-Outerplanar Graphs. In VI Latin-American Algorithms, Graphs and Optimization Symposium, 37:123-128, 2011.
11. A. Montejano, A. Pinlou, A. Raspaud, E. Sopena. Chromatic number of sparse colored mixed planar graphs. In European Conference on Combinatorics, Graph Theory and Applications, EuroComb 2009, 34:363-367, 2009.
12. D. Goncalves, F. Havet, A. Pinlou, S. Thomassé. Spanning galaxies in digraphs. In European Conference on Combinatorics, Graph Theory and Applications, EuroComb 2009, 34:134-137, 2009.
13. A. Montejano, P. Ochem, A. Pinlou, A. Raspaud, E. Sopena. Homomorphisms of 2-edge-colored graphs. In IV Latin-American Algorithms, Graphs and Optimization Symposium, 30:33-38, 2008.
14. M. Montassier, P. Ochem, A. Pinlou. Strong oriented chromatic number of planar graphs without cycles of specifics lengths. In IV Latin-American Algorithms, Graphs and Optimization Symposium, 30:27-32, 2008.
15. L. Esperet, A. Pinlou. Acyclic improper choosability of graphs. In Sixth Czech-Slovak International Symposium on Combinatorics, Graph Theory, Algorithms and Applications, 28:251-258, 2007.
16. P. Ochem, A. Pinlou. Oriented vertex and arc colorings of partial 2-trees. In European Conference on Combinatorics, Graph Theory and Applications (EuroComb '07), 29:195-199, 2007.

### Submitted

1. F. Jacques, A. Pinlou. The chromatic number of signed graphs with bounded maximum average degree. arXiv, 2104.11121, 2021.
2. C. Duffy, F. Jacques, M. Montassier, A. Pinlou. The chromatic number of 2-edge-colored and signed graphs of bounded maximum degree. arXiv, 2009.05439, 2020.

## Teachings Activities

Since Septembre 2017, I teach at Polytech Montpellier. I am head of the Transversal Computer Science Department (« Pôle transversal informatique ») at Polytech Montpellier. I teach information technology and network tools, databases, algorithms, computer programming, and graph theory. All the course materials are available on the learning plateform Moodle.

## Internships Proposal

1. Homomorphisms of signed graphs

Co-supervised by M. Montassier and A. Pinlou
Student: Fabien Jacques (Master 2 - Univ. Bordeaux)

2. $r$-hued coloring and $2$-distance coloring of graphs

Co-supervised by Mickaël Montassier and Alexandre Pinlou
Student: Hoang La (Master 2 – ENS Lyon)

3. Graph colorings and probabilistic methods

Co-supervised by Daniel Gonçalves and Alexandre Pinlou
Student: Charles Guille-Escuret (Licence 3 – ENS Cachan)

4. Albertson and Berman's conjecture

Co-supervised by Mickaël Montassier and Alexandre Pinlou
Student: François Dross (Master 2 - ENS Lyon)

5. Structural properties of graphs via global discharging procedures

Co-supervised by Benjamin Lévêque and Alexandre Pinlou
Student: Marthe Bonamy (Master 2 - ENS Lyon)

6. Graphs of dimension 4

Co-supervised by Daniel Gonçalves and Alexandre Pinlou
Student: Arnaud Mary (Master 2 - Univ. Montpellier)

7. Packing chromatic number

Co-supervised by Stéphane Bessy and Alexandre Pinlou
Student: Cédric Lebrouster (Master 2 – Univ. Montpellier)

## Contact

LIRMM, Université de Montpellier
CC 477, Bât 4