Research Department: 

 Mickael Montassier 
 Université Montpellier 
 LIRMM - UMR 5506 - CC477
 AlGCo Team (Algorithms, Graphs, and Combinatorics)
 161 rue Ada 
 34095 Montpellier Cedex 5 - France

Publications

International journals

[57] 2-distance 4-coloring of planar subcubic graphs with girth at least 21.
Hoang La and Mickael Montassier. To appear in DMTCS, 2024. https://arxiv.org/abs/2106.03587

[56] 2-distance (∆ + 1)-coloring of sparse graphs using the potential method.
Hoang La and Mickael Montassier. To appear in Discrete Mathematics. https://arxiv.org/abs/2103.11687

[55] The chromatic number of 2-edge-colored and signed graphs of bounded maximum degree.
Christopher Duffy, Fabien Jacques, Mickael Montassier, Alexandre Pinlou. To appear in Discrete Mathematics, 2023. https://arxiv.org/abs/2009.05439

[54] 2-distance list (Δ+2)-coloring of planar graphs with girth at least 10.
Hoang La and Mickael Montassier. In Journal of Combinatorial Optimization, 44:1356-1375, 2022. https://doi.org/10.1007/s10878-022-00883-w, 2022. https://arxiv.org/abs/2109.14499

[53] r-hued (r +1)-coloring of planar graphs with girth at least 8 for r >= 9.
H. La, M. Montassier, A. Pinlou, and P. Valicov. In European Journal of Combinatorics, 91:103219, 2021.

[52] Acyclic coloring of graphs and entropy compression method.
D. Gonçalves, M. Montassier, and A. Pinlou. In Discrete Mathematics, 343(4):111772, 2020. http://arxiv.org/abs/1406.4380.

[51] A lower bound on the order of the largest induced linear forest in triangle-free planar graphs.
F. Dross, M. Montassier, and A. Pinlou. In Discrete Mathematics, 342(4):943-950, 2019. https://arxiv.org/abs/1705.11133

[50] Large induced forests in planar graphs with girth 4.
F. Dross, M. Montassier, and A. Pinlou. In Discrete Applied Mathematics, 254:96-106, 2019. http://arxiv.org/abs/1409.1348

[49] Partitioning sparse graphs into an independent set and a forest of bounded degree.
F. Dross, M. Montassier, and A. Pinlou. In Electronic Journal of Combinatorics, 25 (1):1-13, 2018. http://arxiv.org/abs/1606.04394

[48] Partitioning a triangle-free planar graph into a forest and a forest of bounded degree.
F. Dross, M. Montassier, and A. Pinlou. In European Journal of Combinatorics, 66:81-94, 2017. http://arxiv.org/abs/1601.01523

[47] A lower bound on the order of the largest induced forest in planar graphs with high girth.
F. Dross, M. Montassier, and A. Pinlou. In Discrete Applied Mathematics, 214:99-107, 2016. http://arxiv.org/abs/1504.01949

[46] Optimal unavoidable sets of types of 3-paths for planar graphs of given girth.
S. Jendrol', M. Macekova, M. Montassier, and R. Sotak. In Discrete Mathematics, 339(2):780-789, 2016.

[45] 3-paths in graphs with bounded maximum average degree.
S. Jendrol', M. Macekova, M. Montassier, and R. Sotak. In Discussiones Mathematicae Graph Theory, 36(2):339-353, 2016.

[44] Near-colorings: non-colorable graphs and NP-completness.
M. Montassier and P. Ochem. In Electronic Journal of Combinatorics, 22(1) P1.57, 2015.

[43] Design of fault tolerant on-board network.
O. Delmas, F. Havet, M. Montassier, and S. Pérennes. In Theoretical Computer Science, 562:75-89, 2015.

[42] Independent domination in cubic graphs.
P. Dorbec, M.A. Henning, M. Montassier, and J. Southey. In Journal of Graph Theory, 80(4):329–349, 2015.

[41] Strong chromatic index of planar graphs with large girth.
G. Chang, M. Montassier, A. Pêcher, and A. Raspaud. In Discussiones Mathematicae Graph Theory, 34(4):723-733, 2014.

[40] Generalized Power Domination in Regular Graphs.
P. Dorbec, M.A. Henning, C. Lowenstein, M. Montassier, and A. Raspaud. In SIAM J. Discrete Math., 27(3):1559–1574, 2013.

[39] On strong edge-colouring of subcubic graphs.
H. Hocquard, M. Montassier, A. Raspaud, and P. Valicov. In Discrete Applied Mathematics, 161(16–17):2467-2479, 2013

[38] Limits of near-coloring of sparse graphs.
P. Dorbec, T. Kaiser, M. Montassier, and A. Raspaud. In Journal of Graph Theory, 75(2):191–202, 2014.

[37] Vertex-partitions of graphs into cographs and stars.
P. Dorbec, M. Montassier, and P. Ochem. In Journal of Graph Theory, 75(1):75-90, 2014.

[36] Locally identifying coloring of graphs.
L. Esperet, S. Gravier, M. Montassier, P. Ochem, and A. Parreau. The Electronic Journal of Combinatorics, Volume 19, Issue 2, P40, 2012. (EJC) (arXiv)

[35] L(p,q)-labeling of sparse graphs.
C. Charpentier, M. Montassier, and A. Raspaud. In Journal of Combinatorial Optimization, 25(4):646-660, 2013. (here)

[34] Generalized power domination of graphs.
G. J. Chang, P. Dorbec, M. Montassier, and A. Raspaud. In Discrete Applied Mathematics, 160(12):1691 - 1698, 2012. (here)

[33] A complexity dichotomy for the coloring of sparse graphs.
L. Esperet, M. Montassier, P. Ochem, and A. Pinlou. In Journal of Graph Theory, 73(1):85-102, 2013. (here)

[32] Adjacent vertex-distinguishing edge coloring of graphs.
H. Hocquard and M. Montassier. In Journal of Combinatorial Optimization, DOI:10.1007/s10878-011-9444-9, 2012. (here)

[31] Covering a graph by forests and a matching.
T. Kaiser, M. Montassier, and A. Raspaud. In SIAM Journal on Discrete Mathematics, 25(4):1804 - 1811, 2011. (SIAM-DM)(arXiv)

[30] (k,j)-coloring of sparse graphs.
O.V. Borodin, A.O. Ivanova, M. Montassier, and A. Raspaud. In Discrete Applied Mathematics, 159(17):1947 - 1953, 2011. (here)

[29] On two variations of identifying codes.
O. Delmas, S. Gravier, M. Montassier, and A. Parreau. In Discrete Mathematics, 311(17):1948 - 1956, 2011. (DM)(arXiv)

[28] Some structural properties of planar graphs and their applications to 3-choosability.
M. Chen, M. Montassier, and A. Raspaud. In Discrete Mathematics, 312(2):362-373, 2012. (here)

[27] Decomposing graphs into forests.
M. Montassier, P. Ossona de Mendez, A. Raspaud, and X. Zhu. In Journal of Combinatorial Theory, Series B, 102(1):38-52, 2012. (here)

[26] (k,1)-coloring of sparse graphs.
O.V. Borodin, A.O. Ivanova, M. Montassier, and A. Raspaud. In Discrete Mathematics, 312(6):1128-1135, 2012. (here)

[25] Backbone coloring of graphs.
Y. Bu, M. Montassier, A. Raspaud, and W. Wang. In Journal of Combinatorial Optimization, 23(1):79-93, 2012. (here)

[24] Decomposition of sparse graphs into two forests, one having bounded maximum degree.
M. Montassier, A. Raspaud, and X. Zhu. In Information Processing Letters, 110(20):913-916, 2010. (here)

[23] A note on the acyclic 3-choosability of some planar graphs.
H. Hocquard, M. Montassier, and A. Raspaud. In Discrete Applied Mathematics 158(10):1104-1110, 2010. (here)

[22] Decomposition of sparse graphs, with application to game coloring number.
M. Montassier, A. Pêcher, A. Raspaud, D. West, and X. Zhu. In Discrete Mathematics 310(10-11):1520-1523, 2010. (here)

[21] Vertex decompositions of sparse graphs into an edgeless subgraph and a subgraph of maximum degree at most k.
O.V. Borodin, A.O. Ivanova, M. Montassier, P. Ochem, and A. Raspaud. In Journal of Graph Theory, 65(2):83-93, 2010. (here)

[20] Planar graphs without adjacent cycles of length at most seven are 3-colorable.
O.V. Borodin, M. Montassier, and A. Raspaud. In Discrete Mathematics, 310(1):167-173, 2010. (here)

[19] Every planar graph without cycles of length 4 to 12 is acyclically 3-choosable.
H. Hocquard and M. Montassier. In Information Processing Letters, 109(21-22):1193-1196, 2009. (here)

[18] On the 3-colorability of planar graphs without 4-, 7- and 9-cycles.
Y. Bu, H. Lu, M. Montassier, A. Raspaud, W. Wang, and Y. Wang. In Discrete Mathematics 309(13):4596-4607, 2009. (here)

[17] Adapted list colouring of planar graphs.
L. Esperet, M. Montassier, and X. Zhu. In Journal of Graph Theory, 62(2):127-138, 2009. (here)

[16] Star coloring of sparse graphs.
Y. Bu, D.W. Cranston, M. Montassier, A. Raspaud, and W. Wang. In Journal of Graph Theory, 62(3):201-219, 2009. (here)

[15] Planar graphs without 5- and 7-cycles and without adjacent triangles are 3-colorable.
O.V. Borodin, A.N. Glebov, M. Montassier, and A. Raspaud. In Journal of Combinatorial Theory, Series B, 99(4):668-673, 2009. (here)

[14] An upper bound on the adaptable choosability of graphs.
M. Montassier, A. Raspaud, and X. Zhu. In European Journal of Combinatorics, 30(2):351-355, 2009. (here)

[13] A relaxation of Havel's 3-Color Problem.
M. Montassier, A. Raspaud, W. Wang, and Y. Wang. In Information Processing Letters, 107(3-4):107-109, 2008. (here)

[12] Strong oriented chromatic number of planar graphs without short cycles.
M. Montassier, P. Ochem, and A. Pinlou. In DMTCS, 10(1):1-24, 2008. (here)

[11] Linear choosability of graphs.
L. Esperet, M. Montassier, and A. Raspaud. In Discrete Mathematics, 308(17):3938-3950, 2008. (here)

[10] A small non-Z4-colorable planar graph.
M. Montassier. In Discrete Mathematics, 307(13):1684-1686, 2007. (here)

[9] Acyclic 5-choosability of planar graphs without small cycles.
M. Montassier, A. Raspaud, and W. Wang. In Journal of Graph Theory, 54(3):245-260, 2007. (here)

[8] Bordeaux 3-color Conjecture and 3-choosability.
M. Montassier, A. Raspaud, and W. Wang. In Discrete Mathematics, 306(6):573-579, 2006. (here)

[7] Acyclic 4-choosability of planar graphs without cycles of specific length.
M. Montassier, A. Raspaud, and W. Wang. In Algorithms and Combinatorics, 26:473-491, 2006. (here)

[6] A note on the not 3-choosability of some families of planar graphs.
M. Montassier. In Information Processing Letters, 99(2):68-71, 2006. (here)

[5] A note on 2-facial coloring of plane graphs.
M. Montassier and A. Raspaud. In Information Processing Letters, 98(6):235-241, 2006. (here)

[4] Acyclic 4-choosability of planar graphs with girth at least 5.
M. Montassier. Trends in Mathematics: Graph Theory in Paris, 299-310, 2007. (here)

[3] On the acyclic choosability of graphs.
M. Montassier, P. Ochem, and A. Raspaud. In Journal of Graph Theory, 51(4):281-300, 2006. (here)

[2] (d,1)-total labeling of graphs with given maximum average degree.
M. Montassier and A. Raspaud. In Journal of Graph Theory, 51(2):93-109, 2006. (here)

[1] (d,1)-total labeling of planar graphs with large girth and high maximum degree.
F. Bazzaro, M. Montassier, and A. Raspaud. In Discrete Mathematics, 307(16):2141-2151, 2007. (here)

Conferences

[24] 2-distance (Delta+1)-coloring of sparse graphs using the potential method.
Hoang La, Mickael Montassier. In European Conference on Combinatorics, Graph Theory and Applications, EuroComb 2021, Barcelona, Spain. 6-10 september, 2021.

[23] The chromatic number and switching chromatic number of 2-edge-colored graphs of bounded degree.
F. Jacques, M. Montassier, and A. Pinlou. In BGW2019 Bordeaux Graph Workshop, Bordeaux, France. October 28-31, 2019.

[22] r-hued coloring of planar graphs with girth at least 8.
Hoang La, Mickael Montassier, Alexandre Pinlou, and Petru Valicov. In BGW2019 Bordeaux Graph Workshop, Bordeaux, France. October 28-31, 2019.

[21] Partitioning sparse graphs into an independent set and a forest of bounded degree.
F. Dross, M. Montassier, and A. Pinlou. In BGW2016 Bordeaux Graph Workshop, Bordeaux, France. November 7-10, 2016.

[20] Partitioning a triangle-free planar graph into a forest and a forest of bounded degree.
F. Dross, M. Montassier, and A. Pinlou. In European Conference on Combinatorics, Graph Theory and Applications, EuroComb 2015, Bergen, Norway. August 31-September 4, 2015.

[19] Entropy compression method applied to graph colorings.
D. Gonçalves, M. Montassier, and A. Pinlou. ICGT 2014, 9th International colloquium on graph theory and combinatorics, Grenoble, France. June 30-July 4, 2014

[18] Contact Representations of Planar Graph: Rebuilding is Hard.
S. Chaplick, P. Dorbec, J. Kratochvil, M. Montassier, and J. Stacho. In WG2014, Le Domaine de Chalès, Orléans, France. June 25-27, 2014.

[17] Strong chromatic index of planar graphs with large girth.
M. Montassier, A. Pêcher, and A. Raspaud. In EuroComb 2013, Pisa, Italy. September 9-13, 2013.

[16] A note on strong edge-colouring.
H. Hocquard, M. Montassier, A. Raspaud, and P. Valicov. In Bordeaux Graph Workshop 2012, Bordeaux, France. November 21-24, 2012.

[15] Minmax degree of planar graphs.
C. Charpentier, M. Montassier, and A. Raspaud. In EuroComb 2011, Rényi Institute, Budapest, Hungary. August 29-September 2, 2011.

[14] Adjacent vertex-distinguishing edge coloring of graphs with maximum degree at least five.
H. Hocquard and M. Montassier. In EuroComb 2011, Rényi Institute, Budapest, Hungary. August 29-September 2, 2011.

[13] Covering a graph by forests and a matching.
T. Kaiser, M. Montassier, A. Raspaud, and O. Rucky. In CanaDAM 2011, University of Victoria, BC, Canada. May 31-June 3, 2011.

[12] Decomposing a graph into forests.
M. Montassier, P. Ossona de Mendez, A. Raspaud, and X. Zhu. In 8FCC: 8th French Combinatorial Conference. Université Paris Sud. June 28-July 2, 2010.

[11] Identifying colorings of graphs.
L. Esperet, S. Gravier, M. Montassier, P. Ochem, and A. Parreau. In 8FCC: 8th French Combinatorial Conference. Université Paris Sud. June 28-July 2, 2010.

[10] Generalized power domination.
G. J. Chang, P. Dorbec, M. Montassier, and A. Raspaud. In 8FCC: 8th French Combinatorial Conference. Université Paris Sud. June 28-July 2, 2010.

[9] Acyclic choosability of planar graphs : a Steinberg like approach.
H. Hocquard and M. Montassier. An extended abstract in EuroComb'09, European conference on Combinatorics, Graph Theory and Applications. Bordeaux September 7-11, 2009. (here)

[8] Strong oriented chromatic number of planar graphs without cycles of specific lengths.
M. Montassier, P. Ochem, and A. Pinlou. LAGOS '07: Latin-American Algorithms, Graphs and Optimization Symposium. Puerto Varas, Chile, November 25-29, 2007. (here)

[7] Acyclic choosability of graphs.
M. Montassier. A survey in CS06, Sixth Czech-Slovak International Symposium on Combinatorics, Graph Theory, Algorithms and Applications, Prague, July 10-15, 2006. (here)

[6] Linear choosability of graphs.
L. Esperet, M. Montassier, and A. Raspaud. An extended abstract in EuroComb'05, European conference on Combinatorics, Graph Theory and Applications. Berlin, September 5-9, 2005. DMTCS proc. AE, 2005, p.99-104. (here)

[5] Acyclic choosability of graphs with small maximum degree.
D. Gonçalves and M. Montassier. In WG 2005, 31st International Workshop on Graph Theoretic Concepts in Computer Science. Metz, France. June 23-25, 2005. D. Kratsch (Ed.): WG2005, LNCS 3787, p.239-248, Springer-Verlag. (here)

[4] Assignation de fréquences et étiquetage (d,1)-total dans les topologies planaires.
F. Bazzaro, M. Montassier, and A. Raspaud. In 6ème Rencontres Francophones sur les aspects Algorithmiques des Télécommunications ALGOTEL 2004, p.27-31, Batz-sur-mer, France, 26-28 Mai 2004. Institut National de Recherche en Informatique et Automatique. (here)

[3] On the acyclic choosability of graphs.
M. Montassier, P. Ochem, and A. Raspaud. In GT'O4 Graph Theory 2004: a conference in memory of Claude Berge. Paris, July 5-9, 2004. (here)

[2] Observability of recursive clique-trees.
M. Montassier. In Eurocomb'03. European conference on Combinatorics, Graph Theory and Applications. Prague, September 8-12, 2003. (here)

[1] Réseaux de télécommunication minimaux embarqués tolérants aux pannes.
J-C.Bermond, O. Delmas, F. Havet, M. Montassier, and S. Pérennes. In 5ème Rencontres Francophones sur les aspects Algorithmiques des Télécommunications ALGOTEL 2003, p.27-32, Banyuls-sur-mer, France, 12-14 mai 2003. Institut National de Recherche en Informatique et Automatique. ISBN 2-7261-1246-3. (here)

Conferences, invited talks

[7] Vertex-partitions of graphs.
2016 International Conference on Graph Theory, Combinatorics, and Applications, October 29-31, 2016. Zhejiang Normal University, Jinhua, China. (here)

[6] Entropy compression method and graph coloring problems.
C&C 2014, 23rd Workshop on Cycles and Colourings, September 7-12, 2014. Nový Smokovec, High Tatras, Slovakia. (here)

[5] Limits of near-coloring of sparse graphs.
2012 International Conference on Graph Theory, Combinatorics, and Applications, October 26-29, 2012. Zhejiang Normal University, Jinhua, China. (here)

[4] Le problème des 3 couleurs et la conjecture de Steinberg.
JGA 2011, Journées Graphes et Algorithmes, 16-18 Novembre 2011. Université Lyon 1, Lyon, France. (here)

[3] Decomposition of sparse graphs, with applications to game coloring number.
2010 Seminar on Graph Theory, March 19-20, 2010, Department of Applied Mathematics, National Sun Yat-sen University, Kaohsiung, Taiwan. (here)

[2] The 3-Color Problem.
2009 Workshop on Graph Theory, January 10-14, 2009, Department of Applied Mathematics, National Sun Yat-sen University, Kaohsiung, Taiwan. (here)

[1] Adaptive choosability of planar graphs.
Seminar Colorings '08, Department of Applied Mathematics, National Sun Yat-sen University, Kaohsiung, Taiwan. 2008/26/01. (here)

Manuscripts

2-distance (Δ + 2)-coloring of sparse graphs.
Hoang La and Mickael Montassier, 2021. https://arxiv.org/abs/2109.11927

Research Reports

Design of fault tolerant on-board network.
O. Delmas, F. Havet, M. Montassier, and S. Pérennes.
Research Report RR-1345-05. Revised version, January 2010.

Steinberg's Conjecture and near-colorings.
G.J. Chang, F. Havet, M. Montassier, and A. Raspaud.
Research Report RR-7669, INRIA, 7 2011.

Acyclic coloring of graphs with maximum degree five.
H. Hocquard and M. Montassier.
Research report RR-1450-08. Revised version, 2010.

(d,1)-total labelling of sparse graphs.
L. Esperet, M. Montassier, and A. Raspaud.
Research Report RR-1391-06, March 2006.
Revised version, January 2008.

A smaller not 3-choosable planar graph without 4- and 5-cycles.
M. Montassier.
Research Report RR-1361-05, July 2005.

Coloration acyclique par liste et Méthodes probabilistes.
M. Montassier and O. Serra.
6èmes Journées "Graphes et Algorithmes" Laboratoire Leibniz - Grenoble - Septembre 2004. Publié dans Les Cahiers du laboratoire Leibniz 114 (ISSN 1298-020X).

Workshops & Seminars

Entropy compression method applied to graph colorings.
Séminaire Graphes et Structures Discrètes, ENS de Lyon, 2014/05/13.

Méthode de compression et colorations de graphes.
Séminaire Graphes et Applications, LaBRI, Bordeaux. 2013/02/10.

Vertex-partitions of graphs into cographs and stars.
Séminaire AlGCo, LIRMM, Montpellier. 2011/03/24.

Vertex-partitions of graphs into cographs and stars.
GRATEL meeting, National Taipei University, Taipei, Taiwan. 2011/03/12.

Nine Dragon Tree Conjectures.
GRATOS meeting, LIRMM, Montpellier. 2010/12/09.

Near-coloring of sparse graphs.
Tamkang University, Taipei, Taiwan. 2010/03/16.

(k,j)-coloring of sparse graphs.
Graph Theory 2009 , Fredericia, Denmark. 2009/11/27. (here)

Decomposition of sparse graphs, application to game coloring number.
LIRMM, Montpellier, France. 2009/11/12. (here)

Near coloring of sparse graphs.
LIRMM, Montpellier, France. 2009/10/16.(here)

The 3-Color Problem.
University of Ilmenau, Ilmenau, Germany. 2008/10/29.

A relaxation of Havel's Problem.
Normal Zhejiang University, Jinhua, China. 2008/05/06.

Coloration orientée forte de graphes.
JGA'07, Institut Henri Poincaré, Paris. 2007/11/08. (here)

Acyclic choosability of graphs.
Shangaï University, Shangaï, China. 2007/09/12.

(Strong) Oriented colorings of graphs.
Normal Zhejiang University, Jinhua, China. 2007/09/04.

On 3-choosability of graphs.
COMBSTRU, Charles University, Prague, Czech Republic. 2006/03/10.

l-facial coloring and l-facial choosability of graphs.
Comenius University, Bratislava, Slovak Republic. 2005/06/20.

About acyclic choosability of graphs.
COMBSTRU, Mathematical Institute, Oxford, England. 2005/04/11.

Acyclic choosability of graphs with given maximum average degree.
Comenius University, Bratislava, Slovak Republic. 2004/11/06.

Colorations acycliques par liste et méthodes probabilistes.
JGA'04, Laboratoire Leibniz, Grenoble, France. 2004/09/29. (here)

Coloration (d,1)-totale des graphes de degré maximum donné.
Séminaire MASCOTTE, INRIA, Sophia-Antipolis, France. 2004/02/17. (here)

Observabilité des arbres récursifs de cliques.
JGA'03, LE2I, Dijon, France. 2003/04/3.

"Habilitation à diriger des recherches"

On some coloring problems of graphs.
November 17, 2010.
Reviewers: F. Havet, A. Kostochka, and C. Thomassen.
Jury: F. Havet, A. Raspaud, E. Sopena, W. Wang, and X. Zhu.

Vertex-partitions of planar graphs

The 3-Color Problem