Publications

Publications #

Submitted papers #

Optimal Adjacency Labels for Subgraphs of Cartesian Products (with N. Harms and V. Zamaraev), arXiv
Sparse graphs with bounded induced cycle packing number have logarithmic treewidth (with M. Bonamy, É. Bonnet, H. Déprés, C. Geniet, C. Hilaire, S. Thomassé, and A. Wesolek), arXiv
Colouring Strong Products (with D.R. Wood), arXiv
Sparse universal graphs for planarity (with G. Joret and P. Morin), arXiv

Accepted papers #

Asymptotic dimension of minor-closed families and Assouad-Nagata dimension of surfaces (with M. Bonamy, N. Bousquet, C. Groenland, C.-H. Liu, F. Pirot, and A. Scott)
Journal of the European Mathematical Society (2021), arXiv

2020-2024 #

Sketching Distances in Monotone Graph Classes (with N. Harms and A. Kupavskii)
26th International Conference on Randomization and Computation (RANDOM 2022). arXiv
Testability and local certification of monotone properties in minor-closed classes (with S. Norin)
49th EATCS International Colloquium on Automata, Languages and Programming (ICALP 2022). doi, arXiv
Local certification of graphs on surfaces (with B. Lévêque)
Theoretical Computer Science 909 (2022), 68-75. doi, arXiv
Local boxicity (with L. Lichev)
European Journal of Combinatorics 102 (2022), 103495. doi, arXiv
Clustered 3-colouring graphs of bounded degree (with V. Dujmović, P. Morin, B. Walczak, and D.R. Wood)
Combinatorics, Probability and Computing 31(1) (2022), 123-135. doi, arXiv
Adjacency Labelling for Planar Graphs (and Beyond) (with V. Dujmović, C. Gavoille, G. Joret, P. Micek, and P. Morin)
Journal of the ACM 68(6) (2021), Article 42, 1-33. doi, arXiv
Preliminary version in the 61st Annual IEEE Symposium on Foundations of Computer Science (FOCS 2020), doi
Distributed coloring and the local structure of unit-disk graphs (with S. Julliot and A. de Mesmay)
17th International Symposium on Algorithms and Experiments for Wireless Sensor Networks (ALGOSENSORS 2021), doi, arXiv
Packing and covering balls in graphs excluding a minor (with N. Bousquet, W. Cames van Batenburg, G. Joret, W. Lochet, C. Muller, and F. Pirot)
Combinatorica 41(3) (2021), 299-318, doi, arXiv
Isometric universal graphs (with C. Gavoille and C. Groenland)
SIAM Journal on Discrete Mathematics 35(2) (2021), 1224-1237, doi, arXiv
Single-conflict colouring (with Z. Dvořák, R.J. Kang and K. Ozeki)
Journal of Graph Theory 97(1) (2021), 148-160, doi, arXiv
Distributed algorithms for fractional coloring (with N. Bousquet and F. Pirot)
28th International Colloquium on Structural Information and Communication Complexity (SIROCCO 2021), doi, arXiv
Optimal labelling schemes for adjacency, comparability and reachability (with M. Bonamy, C. Groenland, and A. Scott)
53rd Annual ACM Symposium on Theory of Computing (STOC 2021), doi, arXiv
Local approximation of the Maximum Cut in regular graphs (with E. Bamas)
Theoretical Computer Science 820 (2020), 45-59, doi, arXiv
Preliminary version in the 45th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2019), doi
Planar graphs have bounded nonrepetitive chromatic number (with V. Dujmović, G. Joret, B. Walczak, and D.R. Wood)
Advances in Combinatorics 2020:5, 11pp, doi, arXiv
Bipartite complements of circle graphs (with M. Stehlík)
Discrete Mathematics 343(6) (2020), 111834, doi, arXiv

2015-2019 #

Distributed coloring in sparse graphs with fewer colors (with P. Aboulker, M. Bonamy and N. Bousquet)
Electronic Journal of Combinatorics 26(4) (2019), P4.20, doi, arXiv
A preliminary version appeared in the 2018 ACM Symposium on Principles of Distributed Computing (PODC 2018) doi
Separation choosability and dense bipartite induced subgraphs (with R.J. Kang and S. Thomassé)
Combinatorics, Probability and Computing 28(5) (2019), 720-732, doi, arXiv
Partial results from this paper were presented at the 10th International Colloquium on Graph Theory and Combinatorics (ICGT 2018), under the title On dense bipartite induced subgraphs
Exact distance coloring in trees (with N. Bousquet, A. Harutyunyan, and R. de Joannis de Verclos)
Combinatorics, Probability and Computing 28(2) (2019), 177-186, doi, arXiv
Improper coloring of graphs on surfaces (with I. Choi)
Journal of Graph Theory 91(1) (2019), 16-34, doi, arXiv
Distributed coloring of graphs with an optimal number of colors (with E. Bamas)
36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019), doi, arXiv
Boxicity, poset dimension, and excluded minors (with V. Wiechert)
Electronic Journal of Combinatorics 25(4) (2018), #P4.51, doi, arXiv
The width of quadrangulations of the projective plane (with M. Stehlík)
Journal of Graph Theory 89(1) (2018), 76-88, doi, arXiv
Additive bases and flows in graphs (with R. de Joannis de Verclos, T.-N. Le, and S. Thomassé)
SIAM Journal on Discrete Mathematics 32(1) (2018), 534-542, doi, arXiv
A preliminary version appeared in the 2017 European Conference on Combinatorics, Graph Theory and Applications (Eurocomb 2017), doi
Polynomial expansion and sublinear separators (with J.F. Raymond)
European Journal of Combinatorics 69 (2018), 49-53, doi, arXiv
Coloring Jordan regions and curves (with W. Cames van Batenburg and T. Müller)
SIAM Journal on Discrete Mathematics 31(3) (2017), 1670-1684, doi, arXiv
Flows and bisections in cubic graphs (with G. Mazzuoccolo and M. Tarsi)
Journal of Graph Theory 86(2) (2017), 149-158, doi, arXiv
Small feedback vertex sets in planar digraphs (with L. Lemoine and F. Maffray)
Electronic Journal of Combinatorics 24(2) (2017), #P2.6, doi, arXiv
Box representations of embedded graphs
Discrete & Computational Geometry 57(3) (2017), 590-606, doi, arXiv
Graphs with no induced five-vertex path or antipath (with M. Chudnovsky, L. Lemoine, P. Maceli, F. Maffray, and I. Penev)
Journal of Graph Theory 84(3) (2017), 221-232, doi, arXiv
Long induced paths in graphs (with L. Lemoine and F. Maffray)
European Journal of Combinatorics 62 (2017), 1-14, doi, arXiv
Coloring non-crossing strings (with D. Gonçalves and A. Labourel)
Electronic Journal of Combinatorics 23(4) (2016), #P4.4, doi, arXiv
A preliminary version appeared in the 2009 European Conference on Combinatorics, Graph Theory and Applications (EuroComb 2009) under the title Coloring a set of touching strings
The structure of graphs with Circular flow number 5 or more, and the complexity of their recognition problem (with G. Mazzuoccolo and M. Tarsi)
Journal of Combinatorics 7(2) (2016), 453-479, doi, arXiv
Restricted frame graphs and a conjecture of Scott (with J. Chalopin, Z. Li, and P. Ossona de Mendez)
Electronic Journal of Combinatorics 23(1) (2016), #P1.30, doi, arXiv
Islands in graphs on surfaces (with P. Ochem)
SIAM Journal on Discrete Mathematics 30(1) (2016), 206-219, doi, arXiv
Boxicity and topological invariants
European Journal of Combinatorics 51 (2016), 495-499, doi, arXiv
(I realised after the publication of this paper that the bound I obtained as a function of the number of edges had been proved independently in this paper).
Equitable partition of graphs into induced forests (with L. Lemoine and F. Maffray)
Discrete Mathematics 338(8) (2015), 1481-1483, doi, arXiv
On the maximum fraction of edges covered by t perfect matchings in a cubic bridgeless graph (with G. Mazzuoccolo)
Discrete Mathematics 338(8) (2015), 1509-1514, doi, arXiv

2010-2014 #

On cubic bridgeless graphs whose edge-set cannot be covered by four perfect matchings (with G. Mazzuoccolo)
Journal of Graph Theory 77(2) (2014), 144-157, doi, arXiv
A preliminary version appeared in the 2013 European Conference on Combinatorics, Graph Theory and Applications (Eurocomb 2013), doi
Coloring planar graphs with three colors and no large monochromatic components (with G. Joret)
Combinatorics, Probability and Computing 23(4) (2014), 551-570, doi, arXiv
List-coloring claw-free graphs with small clique number (with A. Gyárfás, and F. Maffray)
Graphs and Combinatorics 30(2) (2014), 365-375, doi, pdf
Distance-two coloring of sparse graphs (with Z. Dvořák)
European Journal of Combinatorics 36 (2014), 406-415, doi, arXiv
A unified approach to distance-two colouring of graphs on surfaces (with O. Amini and J. van den Heuvel)
Combinatorica 33(3) (2013), 253-296, doi, arXiv
A preliminary version appeared in the 2009 ACM-SIAM Symposium on Discrete Algorithms (SODA 2009), under the title A unified approach to distance-two colouring of planar graphs, however some arguments there are incorrect and have been corrected in the journal version
Fire containment in planar graphs (with J. van den Heuvel, F. Maffray, and F. Sipma)
Journal of Graph Theory 73(3) (2013), 267-279, doi, arXiv
Boxicity of graphs on surfaces (with G. Joret)
Graphs and Combinatorics 29(3) (2013), 417-427, doi, arXiv
Acyclic edge-coloring using entropy compression (with A. Parreau)
European Journal of Combinatorics 34(6) (2013), 1019-1027, doi, arXiv
A complexity dichotomy for the coloring of sparse graphs (with M. Montassier, P. Ochem, and A. Pinlou)
Journal of Graph Theory 73(1) (2013), 85-102, doi, pdf
The chromatic number of {P5,K4}-free graphs (with L. Lemoine, F. Maffray, and G. Morel)
Discrete Mathematics 313(6) (2013), 743-754, doi, pdf
Locally identifying coloring of graphs (with S. Gravier, M. Montassier, P. Ochem, and A. Parreau)
Electronic Journal of Combinatorics 19(2) (2012), #P40, doi, arXiv
A preliminary version was presented at the 8th French Combinatorial Conference (8FCC).
A superlinear bound on the number of perfect matchings in cubic bridgeless graphs (with F. Kardos and D. Král')
European Journal of Combinatorics 33(5) (2012), 767-798, doi, arXiv
A preliminary version appeared in the 2009 European Conference on Combinatorics, Graph Theory and Applications (EuroComb 2009), under the title Cubic bridgeless graphs have more than a linear number of perfect matchings, doi
Exponentially many perfect matchings in cubic graphs (with F. Kardos, A. King, D. Král', and S. Norine)
Advances in Mathematics 227 (2011), 1646-1664, doi, arXiv
Dynamic list coloring of bipartite graphs
Discrete Applied Mathematics 158(17) (2010), 1963-1965, doi, pdf
Covering line graphs with equivalence relations (with J. Gimbel and A. King)
Discrete Applied Mathematics 158(17) (2010), 1902-1907, doi, arXiv
An improved linear bound on the number of perfect matchings in cubic graphs (with D. Král', P. Skoda, and R. Skrekovski)
European Journal of Combinatorics 31 (2010), 1316-1334, doi, arXiv
Acyclic t-improper colourings of graphs with bounded maximum degree (with L. Addario-Berry, R.J. Kang, C.J.H. McDiarmid, and A. Pinlou)
Discrete Mathematics 310(2) (2010), 223-229, doi, pdf
A preliminary version was presented at the 2007 British Combinatorial Conference (BCC 2007).

2005-2009 #

A functional programming approach for an energy planning problem (with J. Darlay, Y. Kieffer, G. Naves and V. Weber)
24th European conference on Operational Research (EURO 2010).
Adapted list colouring of planar graphs (with M. Montassier, and X. Zhu)
Journal of Graph Theory 62(2) (2009), 127-138, doi, pdf
Game colouring of the square of graphs (with X. Zhu)
Discrete Mathematics 309(13) (2009), 4514-4521, doi, pdf
Boxicity of graphs with bounded degree
European Journal of Combinatorics 30(5) (2009), 1277-1280, doi, pdf
On circle graphs with girth at least five (with P. Ochem)
Discrete Mathematics 309(8) (2009), 2217-2222, doi, pdf
A preliminary version appeared in the 2007 European Conference on Combinatorics, Graph Theory and Applications (EuroComb 2007), doi
On induced-universal graphs for the class of bounded-degree graphs (with A. Labourel, and P. Ochem)
Information Processing Letters 108(5) (2008), 255-260, doi, pdf
Linear choosability of graphs (with M. Montassier, and A. Raspaud)
Discrete Mathematics 308(17) (2008), 3938-3950, doi, pdf
A preliminary version appeared in the 2005 European Conference on Combinatorics, Graph Theory and Applications (EuroComb 2005), proc.
Oriented coloring of 2-outerplanar graphs (with P. Ochem)
Information Processing Letters 101(5) (2007), 215-219, doi, pdf
Acyclic improper choosability of graphs (with A. Pinlou)
6th Czech-Slovak International Symposium on Combinatorics, Graph Theory, Algorithms and Applications (CS 2006), doi, pdf

Theses #

Graph colorings, flows and perfect matchings
Habilitation thesis, Université Grenoble Alpes, 2017, pdf
Distance-two colorings of graphs
PhD thesis, Université Bordeaux 1, 2008.

Other manuscripts #

Antifactors in bipartite multigraphs
Manuscript, 2022, arXiv
Surfaces have (asymptotic) dimension 2 (with M. Bonamy, N. Bousquet, C. Groenland, F. Pirot, and A. Scott)
Manuscript, 2020, arXiv (mostly superceded by this paper)
Coloring graphs with no induced subdivision of K4+ (with N. Trotignon)
Manuscript, 2019, arXiv
Frugal Colouring of Graphs (with O. Amini and J. van den Heuvel)
LaBRI, Université Bordeaux 1, Research Report RR-1428-07, May 2007, arXiv
(d,1)-total labelling of sparse graphs (with M. Montassier, and A. Raspaud)
LaBRI, Université Bordeaux 1, Research Report RR-1391-06, March 2006, pdf

Coauthors #

Pierre Aboulker, Louigi Addario-Berry, Omid Amini, Etienne Bamas, Marthe Bonamy, Édouard Bonnet, Nicolas Bousquet, Wouter Cames van Batenburg, Jérémie Chalopin, Ilkyoo Choi, Maria Chudnovsky, Julien Darlay, Hugues Déprés, Vida Dujmović, Zdenek Dvořák, Cyril Gavoille, Colin Geniet, John Gimbel, Daniel Gonçalves, Sylvain Gravier, Carla Groenland, András Gyárfás, Nathaniel Harms, Ararat Harutyunyan, Claire Hilaire, Jan van den Heuvel, Rémi de Joannis de Verclos, Gwenaël Joret, Sébastien Julliot, Ross J. Kang, Frantisek Kardos, Dan Kral', Yann Kieffer, Andrew D. King, Andrey Kupavskii, Arnaud Labourel, Tien-Nam Le, Laetitia Lemoine, Benjamin Lévêque, Zhentao Li, Lyuben Lichev, Chun-Hung Liu, William Lochet, Peter Maceli, Frédéric Maffray, Giuseppe Mazzuoccolo, Colin J.H. McDiarmid, Arnaud de Mesmay, Piotr Micek, Mickaël Montassier, Grégory Morel, Pat Morin, Carole Muller, Tobias Müller, Guyslain Naves, Sergey Norin, Pascal Ochem, Patrice Ossona de Mendez, Kenta Ozeki, Aline Parreau, Irena Penev, Alexandre Pinlou, François Pirot, André Raspaud, Jean-Florent Raymond, Alex Scott, Félix Sipma, Petr Skoda, Riste Skrekovski, Matej Stehlík, Michael Tarsi, Stéphan Thomassé, Nicolas Trotignon, Bartosz Walczak, Valentin Weber, Alexandra Wesolek, Veit Wiechert, David R. Wood, Viktor Zamaraev, Xuding Zhu.

Hugo