Publications #
Submitted papers #
Long induced paths in sparse graphs and graphs with forbidden patterns (with J. Duron and J.-F. Raymond
Manuscript, 2024, arXiv
Periodic colorings and orientations in infinite graphs (with T. Abrishami, U. Giocanti, M. Hamann, P. Knappe, and R.G. Möller)
Manuscript, 2024, arXiv
2020-2024 #
The structure of quasi-transitive graphs avoiding a minor with applications to the domino problem (with U. Giocanti and C. Legrand-Duchesne)
Journal of Combinatorial Theory, Series B 169 (2024), 561-613, doi, arXiv
Extended abstract in Eurocomb 2023 - European Conference on Combinatorics, Graph Theory and Applications, doi
Colouring Strong Products (with D.R. Wood)
European Journal of Combinatorics 121 (2024), 103847, doi, arXiv
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 26(10) (2024), 3739-3791, doi, arXiv
Local certification of geometric graph classes (with O. Defrain, A. Lagoutte, P. Morin, and J.-F. Raymond)
MFCS 2024 - 49th International Symposium on Mathematical Foundations of Computer Science, doi, arXiv
Coarse geometry of quasi-transitive graphs beyond planarity (with U. Giocanti)
Electronic Journal of Combinatorics 31(2) (2024), P2.41. doi, arXiv
Optimal Adjacency Labels for Subgraphs of Cartesian Products (with N. Harms and V. Zamaraev)
SIAM Journal on Discrete Mathematics 38(3) (2024), 2181-2193. doi, arXiv
Preliminary version in ICALP 2023 - 50th EATCS International Colloquium on Automata, Languages and Programming, doi
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)
Journal of Combinatorial Theory, Series B 167 (2024), 215-249. doi, arXiv
Preliminary version in SODA 2023 - 34th Annual ACM-SIAM Symposium on Discrete Algorithms, doi
Optimization in graphical small cancellation theory (with U. Giocanti)
Discrete Mathematics 347(4) (2024), 113842. doi, arXiv
Sparse universal graphs for planarity (with G. Joret and P. Morin)
Journal of the London Mathematical Society 108(4) (2023), 1333-1357. doi, arXiv
Proof of the Clustered Hadwiger Conjecture (with V. Dujmović, P. Morin, and D.R. Wood)
FOCS 2023 - 64th IEEE Symposium on the Foundations of Computer Science. doi, arXiv
Distributed coloring and the local structure of unit-disk graphs (with S. Julliot and A. de Mesmay)
Theoretical Computer Science 944 (2023), 113674. doi, arXiv
Preliminary version in ALGOSENSORS 2021 - 17th International Symposium on Algorithms and Experiments for Wireless Sensor Networks, doi
Sketching Distances in Monotone Graph Classes (with N. Harms and A. Kupavskii)
RANDOM 2022 - 26th International Conference on Randomization and Computation, doi, arXiv
Testability and local certification of monotone properties in minor-closed classes (with S. Norin)
ICALP 2022 - 49th EATCS International Colloquium on Automata, Languages and Programming, 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 FOCS 2020 - 61st Annual IEEE Symposium on Foundations of Computer Science, doi
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)
SIROCCO 2021 - 28th International Colloquium on Structural Information and Communication Complexity, doi, arXiv
Optimal labelling schemes for adjacency, comparability and reachability (with M. Bonamy, C. Groenland, and A. Scott)
STOC 2021 - 53rd Annual ACM Symposium on Theory of Computing, 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 WG 2019 - 45th International Workshop on Graph-Theoretic Concepts in Computer Science, 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
Preliminary version in PODC 2018 - ACM Symposium on Principles of Distributed Computing 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 ICGT 2018 - 10th International Colloquium on Graph Theory and Combinatorics, 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)
STACS 2019 - 36th International Symposium on Theoretical Aspects of Computer Science, 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
Extended abstract in Eurocomb 2017 - European Conference on Combinatorics, Graph Theory and Applications, 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
Extended abstract in EuroComb 2009 - European Conference on Combinatorics, Graph Theory and Applications 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
Extended abstract in Eurocomb 2013 - European Conference on Combinatorics, Graph Theory and Applications, 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
Preliminary version in SODA 2009 - ACM-SIAM Symposium on Discrete Algorithms, 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
Extended abstract in 8FCC - 8th French Combinatorial Conference.
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
Extended abstract in EuroComb 2009 - European Conference on Combinatorics, Graph Theory and Applications, 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
Extended abstract in BCC 2007 - British Combinatorial Conference.
2005-2009 #
A functional programming approach for an energy planning problem (with J. Darlay, Y. Kieffer, G. Naves and V. Weber)
EURO 2010 - 24th European conference on Operational Research.
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
Extended abstract in EuroComb 2007 - European Conference on Combinatorics, Graph Theory and Applications, 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
Extended abstract in EuroComb 2005 - European Conference on Combinatorics, Graph Theory and Applications, 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)
CS 2006 - 6th Czech-Slovak International Symposium on Combinatorics, Graph Theory, Algorithms and Applications, 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 #
Renaming in distributed certification (with N. Bousquet, L. Feuilloley, and S. Zeitoun )
Manuscript, 2024, arXiv
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, Tara Abrishami, 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, Oscar Defrain, Hugues Déprés, Vida Dujmović, Julien Duron, Zdenek Dvořák, Laurent Feuilloley, Cyril Gavoille, Colin Geniet, John Gimbel, Ugo Giocanti, Daniel Gonçalves, Sylvain Gravier, Carla Groenland, András Gyárfás, Matthias Hamann, 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, Paul Knappe, Andrey Kupavskii, Arnaud Labourel, Aurélie Lagoutte, Tien-Nam Le, Clément Legrand-Duchesne, 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, Rögnvaldur Möller, 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, Sébastien Zeitoun.