My main research area is combinatorics, with a focus on graph theory and partial orders. I especially enjoy working on problems from structural graph theory (treewidth, graph minors, classes of sparse graphs, etc.), graph coloring, applications of the probabilistic method, and the theory of dimension for partial orders. I am also interested in combinatorial optimization, in particular in approximation algorithms.

This is a new journal in graph theory, following the diamond open-access model. Check it out!.

• Integer programs with nearly totally unimodular matrices: the cographic case (with M. Aprile, S. Fiorini, S. Kober, M. T. Seweryn, S. Weltge, and Y. Yuditsky). Extended abstract in proc. of SODA 2025 (to appear).
• Planar graphs in blowups of fans (with V. Dujmović, P. Micek, P. Morin, and D. R. Wood). Extended abstract in proc. of SODA 2025 (to appear).
• A Caro-Wei bound for induced linear forests in graphs (with R. Petit). Preprint.
• Tight bound for the Erdős-Pósa property of tree minors (with V. Dujmović, P. Micek, and P. Morin). Combinatorics, Probability, and Computing, to appear.
• Cliquewidth and dimension (with P. Micek, M. Pilipczuk, and B. Walczak). Extended abstract in proc. of SODA 2024.
• The grid-minor theorem revisited (with V. Dujmović, R. Hickingbotham, J. Hodor, H. La, P. Micek, P. Morin, C. Rambaud, and D. R. Wood). Extended abstract in proc. of SODA 2024.
• Integer programs with bounded subdeterminants and two nonzeros per row (with S. Fiorini, S. Weltge, and Y. Yuditsky). Journal of the ACM, to appear. Extended abstract in proc. of FOCS 2021.
• Information-theoretic lower bounds for quantum sorting (with J. Cardinal and J. Roland). Preprint.
• Pathwidth vs cocircumference (with M. Briański and M. T. Seweryn). SIAM Journal on Discrete Mathematics, 38/1:857–866, 2024.
• The excluded tree minor theorem revisited (with V. Dujmović, R. Hickingbotham, P. Micek, P. Morin, and D. R. Wood). Combinatorics, Probability, and Computing, 33:85–90, 2024.
• Neighborhood complexity of planar graphs (with C. Rambaud). Combinatorica, 44:1115–1148, 2024.
• Tight bound on treedepth in terms of pathwidth and longest path (with M. Hatzel, P. Micek, M. Pilipczuk, T. Ueckerdt, and B. Walczak). Combinatorica, 44:417–427, 2024.
• Product structure extension of the Alon–Seymour–Thomas theorem (with M. Distel, V. Dujmović, D. Eppstein, R. Hickingbotham, P. Micek, P. Morin, M. T. Seweryn, and D. R. Wood). SIAM Journal on Discrete Mathematics, 38/3:2095–2107, 2024.
• Bounded-degree planar graphs do not have bounded-degree product structure (with V. Dujmović, P. Micek, P. Morin, and D. R. Wood). Electronic Journal of Combinatorics, 31/2:P2.51, 2024.
• Edge separators for graphs excluding a minor (with W. Lochet and M. T. Seweryn). Electronic Journal of Combinatorics, 30/4:P4.12, 2023.
• Treedepth vs circumference (with M. Briański, K. Majewski, P. Micek, M. T. Seweryn, and R. Sharma). Combinatorica, 43:659–664, 2023.
• Sparse universal graphs for planarity (with L. Esperet and P. Morin). Journal of the London Mathematical Society, 108/4:1333–1357, 2023.
• Approximating pathwidth for graphs of small treewidth (with C. Groenland, W. Nadara, and B. Walczak). ACM Transactions on Algorithms, 19/2:1–19, 2023. Extended abstract in proc. of SODA 2021.
• Improved bounds for weak coloring numbers (with P. Micek). Electronic Journal of Combinatorics, 29/1:P1.60, 2022.
• Subgraph densities in a surface (with T. Huynh and D. R. Wood). Combinatorics, Probability, and Computing, 31/5:812–839, 2022.
• Excluding a ladder (with T. Huynh, P. Micek, M. T. Seweryn, and P. Wollan). Combinatorica, 42:405–432, 2022.
• Smaller extended formulations for spanning tree polytopes in minor-closed classes and beyond (with M. Aprile, S. Fiorini, T. Huynh, and D. R. Wood). Electronic Journal of Combinatorics, 28/4:P4.47, 2021.
• Tight bounds on the clique chromatic number (with P. Micek, B. Reed, and M. Smid). Electronic Journal of Combinatorics, 28/3:P3.51, 2021.
• Adjacency labelling for planar graphs (and beyond) (with V. Dujmović, L. Esperet, C. Gavoille, P. Micek, and P. Morin). Journal of the ACM, 68/6:Article 42, 2021. Extended abstract in proc. of FOCS 2020.
• Notes on graph product structure theory (with Z. Dvořák, T. Huynh, C.-H. Liu, and D. R. Wood). In: {Wood D.R., de Gier J., Praeger C.E., Tao T.} (eds) 2019-20 MATRIX Annals. MATRIX Book Series, vol 4, 513–533, 2021. Springer.
• Packing and covering balls in graphs excluding a minor (with N. Bousquet, W. Cames van Batenburg, L. Esperet, W. Lochet, C. Muller, and F. Pirot). Combinatorica, 41:299–318, 2021.
• Unavoidable minors for graphs with large ℓp-dimension (with S. Fiorini, T. Huynh, and C. Muller). Discrete and Computational Geometry, 66:301–343, 2021.
• Two lower bounds for p-centered colorings (with L. Dubois, G. Perarnau, M. Pilipczuk, and F. Pitois). Discrete Mathematics and Theoretical Computer Science, 2020.
• Erdős-Pósa from ball packing (with W. Cames van Batenburg and A. Ulmer). SIAM Journal on Discrete Mathematics, 34/3:1609–1619, 2020.
• Large independent sets in triangle-free cubic graphs: beyond planarity (with W. Cames van Batenburg and J. Goedgebeur). Advances in Combinatorics, P7, 45 pp, 2020.
• The stable set problem in graphs with bounded genus and bounded odd cycle packing number (with M. Conforti, S. Fiorini, T. Huynh, and S. Weltge). Extended abstract in proc. of SODA 2020.
• Revisiting a theorem by Folkman on graph colouring (with M. Bonamy, P. Charbit, O. Defrain, A. Lagoutte, V. Limouzy, L. Pastor, and J.-S. Sereni). Electronic Journal of Combinatorics, 27/1:P1.56, 2020.
• Planar graphs have bounded nonrepetitive chromatic number (with V. Dujmović, L. Esperet, B. Walczak, and D. R. Wood). Advances in Combinatorics, P5, 11 pp, 2020.
• Planar graphs have bounded queue-number (with V. Dujmović, P. Micek, P. Morin, T. Ueckerdt, and D. R. Wood). Journal of the ACM, 67/4:Article 22, 2020. Extended abstract in proc. of FOCS 2019.
• Minor-closed graph classes with bounded layered pathwidth (with V. Dujmović, D. Eppstein, P. Morin, and D. R. Wood). SIAM Journal on Discrete Mathematics, 34/3:1693–1709, 2020.
• Progress on the adjacent vertex distinguishing edge colouring conjecture (with W. Lochet). SIAM Journal on Discrete Mathematics, 34/4:2221–2238, 2020.
• Seymour’s conjecture on 2-connected graphs of large pathwidth (with T. Huynh, P. Micek, and D. R. Wood). Combinatorica, 40:839–868, 2020.
• Improved approximation algorithms for hitting 3-vertex paths (with S. Fiorini and O. Schaudt). Mathematical Programming, 182:355–367, 2020. Extended abstract in proc. of IPCO 2016.
• Assortment optimisation under a general discrete choice model: A tight analysis of revenue-ordered assortments (with G. Berbeglia). Algorithmica, 82/4:681–720, 2020. Extended abstract in proc. of EC 2017.
• A tight Erdős-Pósa function for planar minors (with W. Cames van Batenburg, T. Huynh, and J.-F. Raymond). Advances in Combinatorics, P2, 33 pp, 2019. Extended abstract in proc. of SODA 2019.
• Nowhere dense graph classes and dimension (with P. Micek, P. Ossona de Mendez, and V. Wiechert). Combinatorica, 39/5:1055–1079, 2019.
• A tight Erdős-Pósa function for wheel minors (with P. Aboulker, S. Fiorini, T. Huynh, J.-F. Raymond, and I. Sau). SIAM Journal on Discrete Mathematics, 32/3:2302–2312, 2018.
• Burling graphs, chromatic number, and orthogonal tree-decompositions (with S. Felsner, P. Micek, W. T. Trotter, and V. Wiechert). Electronic Journal of Combinatorics, 25/1:P1.35, 2018.
• Orthogonal tree decompositions of graphs (with V. Dujmović, P. Morin, S. Norin, and D. R. Wood). SIAM Journal on Discrete Mathematics, 32/2:839–863, 2018.
• Planar posets have dimension at most linear in their height (with P. Micek and V. Wiechert). SIAM Journal on Discrete Mathematics, 31/4:2754–2790, 2018.
• K_4-minor-free induced subgraphs of sparse connected graphs (with D. R. Wood). SIAM Journal on Discrete Mathematics, 32/1:123–147, 2018.
• Sparsity and dimension (with P. Micek and V. Wiechert). Combinatorica, 38/5:1129–1148, 2018. Extended abstract in proc. of SODA 2016.
• Smaller extended formulations for the spanning tree polytope of bounded-genus graphs (with S. Fiorini, T. Huynh, and K. Pashkovich). Discrete and Computational Geometry, 57/3:757–761, 2017.
• The excluded minors for isometric realizability in the plane (with S. Fiorini, T. Huynh, and A. Varvitsiotis). SIAM Journal on Discrete Mathematics, 31/1:438–453, 2017.
• On the dimension of posets with cover graphs of treewidth 2 (with P. Micek, W. T. Trotter, R. Wang, and V. Wiechert). Order, 34/2:185–234, 2017.
• Pathwidth and nonrepetitive list coloring (with A. Gagol, J. Kozik, and P. Micek). Electronic Journal of Combinatorics, 23/4:P4.40, 2016.
• Tree-width and dimension (with P. Micek, K. G. Milans, W. T. Trotter, B. Walczak, and R. Wang). Combinatorica, 36/4:431–450, 2016.
• Nonrepetitive colouring via entropy compression (with V. Dujmović, J. Kozik, and D. R. Wood). Combinatorica, 36/6:661–686, 2016.
• Reducing the rank of a matroid (with A. Vetta). Discrete Mathematics and Theoretical Computer Science, 17/2:143–156, 2015.
• Hitting all maximal independent sets of a bipartite graph (with J. Cardinal). Algorithmica, 72/2:359–368, 2015.
• Empty pentagons in point sets with collinearities (with J. Barát, V. Dujmović, M. Payne, L. Scharf, D. Schymura, P. Valtr, and D. R. Wood). SIAM Journal on Discrete Mathematics, 29/1:198–209, 2015.
• Coloring planar graphs with three colors and no large monochromatic components (with L. Esperet). Combinatorics, Probability, and Computing, 23/4:551–570, 2014.
• Hitting and harvesting pumpkins (with C. Paul, I. Sau, S. Saurabh, and S. Thomassé). SIAM Journal on Discrete Mathematics, 103/1:1363–1390, 2014. Extended abstract in proc. of ESA 2011.
• A note on the Cops & Robber game on graphs embedded in non-orientable surfaces (with N. E. Clarke, S. Fiorini, and D. O. Theis). Graphs and Combinatorics, 30/1:119–124, 2014.
• Excluded forest minors and the Erdős-Pósa property (with S. Fiorini and D. R. Wood). Combinatorics, Probability, and Computing, 22/5:700–721, 2013.
• A linear-time algorithm for finding a complete graph minor in a dense graph (with V. Dujmović, D. J. Harvey, B. Reed, and D. R. Wood). SIAM Journal on Discrete Mathematics, 27/4:1770–1774, 2013.
• Nonrepetitive colourings of planar graphs with O(log n) colours (with V. Dujmović, F. Frati, and D. R. Wood). Electronic Journal of Combinatorics, 20/1:P51, 2013.
• Boxicity of graphs on surfaces (with L. Esperet). Graphs and Combinatorics, 29/3:417–427, 2013.
• Complete graph minors and the graph minor structure theorem (with D. R. Wood). Journal of Combinatorial Theory, Series B, 103/1:61–74, 2013.
• The Stackelberg minimum spanning tree game on planar and bounded-treewidth graphs (with J. Cardinal, E. D. Demaine, S. Fiorini, I. Newman, and O. Weimann). Journal of Combinatorial Optimization, 25/1:19–46, 2013. Extended abstract in proc. of WINE 2009.
• Sorting under partial information (without the ellipsoid algorithm) (with J. Cardinal, S. Fiorini, R. M. Jungers, and J. I. Munro). Combinatorica, 33/6:655–697, 2013. Extended abstract in proc. of STOC 2010.
• Approximating the balanced minimum evolution problem (with S. Fiorini). Operations Research Letters, 40/1:31–35, 2012.
• An improved bound for First-Fit on posets without two long incomparable chains (with V. Dujmović and D. R. Wood). SIAM Journal on Discrete Mathematics, 26/3:1068–1075, 2012.
• Nordhaus-Gaddum for treewidth (with D. R. Wood). European Journal of Combinatorics, 33/4:488–490, 2012.
• Small minors in dense graphs (with S. Fiorini, D. O. Theis, and D. R. Wood). European Journal of Combinatorics, 33/6:1226–1245, 2012.
• Trees with given stability number and minimum number of stable sets (with V. Bruyère and H. Mélot). Graphs and Combinatorics, 28/2:167–187, 2012.
• Minimum entropy combinatorial optimization problems (with J. Cardinal and S. Fiorini). Theory of Computing Systems, 51/1:4–21, 2012. Extended abstract in proc. of CiE 2009.
• First-Fit is linear on posets excluding two long incomparable chains (with K. G. Milans). Order, 28/3:455–464, 2011.
• Disproof of the list Hadwiger conjecture (with J. Barát and D. R. Wood). Electronic Journal of Combinatorics, 18/1:R232, 2011.
• On the maximum number of cliques in a graph embedded in a surface (with V. Dujmović, G. Fijavž, T. Sulanke, and D. R. Wood). European Journal of Combinatorics, 32/8:1244–1252, 2011.
• Stackelberg network pricing is hard to approximate. Networks, 57/2:117–120, 2011.
• The Stackelberg minimum spanning tree game (with J. Cardinal, E. D. Demaine, S. Fiorini, S. Langerman, I. Newman, and O. Weimann). Algorithmica, 59/2:129–144, 2011. Extended abstract in proc. of WADS 2007.
• Hitting diamonds and growing cacti (with S. Fiorini and U. Pietropaoli). Extended abstract in proc. of IPCO 2010.
• Irreducible triangulations are small (with D. R. Wood). Journal of Combinatorial Theory, Series B, 100/5:446–455, 2010.
• An efficient algorithm for partial order production (with J. Cardinal, S. Fiorini, R. M. Jungers, and J. I. Munro). SIAM Journal on Computing, 39/7:2927–2940, 2010. Extended abstract in proc. of STOC 2009.
• The Cops and Robber game on graphs with forbidden (induced) subgraphs (with M. Kamiński and D. O. Theis). Contributions to Discrete Mathematics, 5/2:40–51, 2010.
• Weighted graphs defining facets: a connection between stable set and linear ordering polytopes (with J.-P. Doignon and S. Fiorini). Discrete Optimization, 6/1:1–9, 2009.
• On a theorem of Sewell and Trotter (with S. Fiorini). European Journal of Combinatorics, 30/2:425–428, 2009.
• Minimum entropy orientations (with J. Cardinal and S. Fiorini). Operations Research Letters, 36/6:680–683, 2008.
• Well-balanced orientations of mixed graphs (with A. Bernáth). Information Processing Letters, 106/4:149–151, 2008.
• Turán’s theorem and k-connected graphs (with N. Bougard). Journal of Graph Theory, 58/1:1–13, 2008.
• Tight results on minimum entropy set cover (with J. Cardinal and S. Fiorini). Algorithmica, 51/1:49–60, 2008. Extended abstract in proc. of APPROX 2006.
• Minimum entropy coloring (with J. Cardinal and S. Fiorini). Journal of Combinatorial Optimization, 16/4:361–377, 2008. Extended abstract in proc. of ISAAC 2005.
• Facets of the linear ordering polytope: a unification for the fence family through weighted graphs (with J.-P. Doignon and S. Fiorini). Journal of Mathematical Psychology, 50/3:251–262, 2006.