Gwenaël Joret - Publications

Publications and preprints

A tight Erdős-Pósa function for planar minors (with W. C. v. Batenburg, T. Huynh, and J.-F. Raymond). Preprint.
Progress on the adjacent vertex distinguishing edge colouring conjecture (with W. Lochet). Preprint.
Seymour’s conjecture on 2-connected graphs of large pathwidth (with T. Huynh, P. Micek, and D. R. Wood). Preprint.
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, accepted.
Nowhere dense graph classes and dimension (with P. Micek, P. Ossona de Mendez, and V. Wiechert). Preprint.
Sparsity and dimension (with P. Micek and V. Wiechert). Combinatorica, to appear. Extended abstract in proc. of SODA 2016.
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. Extended abstract in proc. of Eurocomb 2017.
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₄-minor-free induced subgraphs of sparse connected graphs (with D. R. Wood). SIAM Journal on Discrete Mathematics, 32/1:123--147, 2018.
Assortment optimisation under a general discrete choice model: A tight analysis of revenue-ordered assortments (with G. Berbeglia). Extended abstract in proc. of EC 2017.
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.
Improved approximation algorithms for hitting 3-vertex paths (with S. Fiorini and O. Schaudt). Extended abstract in proc. of IPCO 2016.
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(logn) 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.

Links on issues related to publishing