Gwenaël Joret - Publications

• Home
• Publications
• Curriculum Vitae

Publications and preprints

• Nowhere Dense Graph Classes and Dimension (with P. Micek, P. O. d. Mendez, and V. Wiechert). Preprint.
• Burling graphs, chromatic number, and orthogonal tree-decompositions (with S. Felsner, P. Micek, W. T. Trotter, and V. Wiechert). Extended abstract in proc. of Eurocomb 2017.
• Orthogonal tree decompositions of graphs (with V. Dujmović, P. Morin, S. Norin, and D. R. Wood). Preprint.
• Planar posets have dimension at most linear in their height (with P. Micek and V. Wiechert). Preprint.
• 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.
• K₄-minor-free induced subgraphs of sparse connected graphs (with D. R. Wood). SIAM Journal on Discrete Mathematics, to appear.
• Sparsity and dimension (with P. Micek and V. Wiechert). Combinatorica, to appear. Extended abstract in proc. of SODA 2016.
• On the dimension of posets with cover graphs of treewidth 2 (with P. Micek, W. T. Trotter, R. Wang, and V. Wiechert). Order, to appear.
• 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.
• 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