Gwenaël Joret

According to our database1, Gwenaël Joret authored at least 76 papers between 2005 and 2020.

Collaborative distances:
  • Dijkstra number2 of four.
  • Erdős number3 of two.



In proceedings 
PhD thesis 




Improved approximation algorithms for hitting 3-vertex paths.
Math. Program., 2020

Planar Graphs Have Bounded Queue-Number.
J. ACM, 2020

Sparse universal graphs for planarity.
CoRR, 2020

Approximating pathwidth for graphs of small treewidth.
CoRR, 2020

Tight Bounds on The Clique Chromatic Number.
CoRR, 2020

Two lower bounds for $p$-centered colorings.
CoRR, 2020

Subgraph densities in a surface.
CoRR, 2020

Adjacency Labelling for Planar Graphs (and Beyond).
CoRR, 2020

Excluding a ladder.
CoRR, 2020

Notes on Graph Product Structure Theory.
CoRR, 2020

Packing and covering balls in graphs excluding a minor.
CoRR, 2020

Revisiting a Theorem by Folkman on Graph Colouring.
Electron. J. Comb., 2020

Assortment Optimisation Under a General Discrete Choice Model: A Tight Analysis of Revenue-Ordered Assortments.
Algorithmica, 2020

The stable set problem in graphs with bounded genus and bounded odd cycle packing number.
Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, 2020

Erdős-Pósa from ball packing.
CoRR, 2019

Large independent sets in triangle-free cubic graphs: beyond planarity.
CoRR, 2019

Planar graphs have bounded nonrepetitive chromatic number.
CoRR, 2019

Unavoidable minors for graphs with large 𝓁<sub>p</sub>-dimension.
CoRR, 2019

Information-theoretic lower bounds for quantum sorting.
CoRR, 2019

Nowhere Dense Graph Classes and Dimension.
Comb., 2019

A tight Erdős-Pósa function for planar minors.
Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2019

K<sub>4</sub>-Minor-Free Induced Subgraphs of Sparse Connected Graphs.
SIAM J. Discret. Math., 2018

Corrigendum: Orthogonal Tree Decompositions of Graphs.
SIAM J. Discret. Math., 2018

Orthogonal Tree Decompositions of Graphs.
SIAM J. Discret. Math., 2018

A Tight Erdös-Pósa Function for Wheel Minors.
SIAM J. Discret. Math., 2018

Minor-closed graph classes with bounded layered pathwidth.
CoRR, 2018

Progress on the adjacent vertex distinguishing edge colouring conjecture.
CoRR, 2018

Seymour's conjecture on 2-connected graphs of large pathwidth.
CoRR, 2018

Sparsity and Dimension.
Comb., 2018

Planar Posets Have Dimension at Most Linear in Their Height.
SIAM J. Discret. Math., 2017

The Excluded Minors for Isometric Realizability in the Plane.
SIAM J. Discret. Math., 2017

On the Dimension of Posets with Cover Graphs of Treewidth 2.
Order, 2017

Burling graphs, chromatic number, and orthogonal tree-decompositions.
Electron. Notes Discret. Math., 2017

Smaller Extended Formulations for the Spanning Tree Polytope of Bounded-Genus Graphs.
Discret. Comput. Geom., 2017

$K_{4}$-Minor-Free Induced Subgraphs of Sparse Connected Graphs.
CoRR, 2016

Pathwidth and Nonrepetitive List Coloring.
Electron. J. Comb., 2016

Tree-width and dimension.
Comb., 2016

Nonrepetitive colouring via entropy compression.
Comb., 2016

Empty Pentagons in Point Sets with Collinearities.
SIAM J. Discret. Math., 2015

Reducing the rank of a matroid.
Discret. Math. Theor. Comput. Sci., 2015

Hitting All Maximal Independent Sets of a Bipartite Graph.
Algorithmica, 2015

Hitting and Harvesting Pumpkins.
SIAM J. Discret. Math., 2014

A Note on the Cops and Robber Game on Graphs Embedded in Non-Orientable Surfaces.
Graphs Comb., 2014

Colouring Planar Graphs With Three Colours and No Large Monochromatic Components.
Comb. Probab. Comput., 2014

A Linear-Time Algorithm for Finding a Complete Graph Minor in a Dense Graph.
SIAM J. Discret. Math., 2013

Complete graph minors and the graph minor structure theorem.
J. Comb. Theory, Ser. B, 2013

The Stackelberg minimum spanning tree game on planar and bounded-treewidth graphs.
J. Comb. Optim., 2013

Boxicity of Graphs on Surfaces.
Graphs Comb., 2013

Excluded Forest Minors and the Erdős-Pósa Property.
Comb. Probab. Comput., 2013

Coloring planar graphs with three colors and no large monochromatic components
CoRR, 2013

Nonrepetitive Colourings of Planar Graphs with O(log n) Colours.
Electron. J. Comb., 2013

Sorting under partial information (without the ellipsoid algorithm).
Comb., 2013

An Improved Bound for First-Fit on Posets Without Two Long Incomparable Chains.
SIAM J. Discret. Math., 2012

Approximating the balanced minimum evolution problem.
Oper. Res. Lett., 2012

Minimum Entropy Combinatorial Optimization Problems.
Theory Comput. Syst., 2012

Trees with Given Stability Number and Minimum Number of Stable Sets.
Graphs Comb., 2012

Nordhaus-Gaddum for treewidth.
Eur. J. Comb., 2012

Small minors in dense graphs.
Eur. J. Comb., 2012

First-Fit is Linear on Posets Excluding Two Long Incomparable Chains.
Order, 2011

Stackelberg network pricing is hard to approximate.
Networks, 2011

On the maximum number of cliques in a graph embedded in a surface.
Eur. J. Comb., 2011

Nonrepetitive Colouring via Entropy Compression
CoRR, 2011

Disproof of the List Hadwiger Conjecture.
Electron. J. Comb., 2011

The Stackelberg Minimum Spanning Tree Game.
Algorithmica, 2011

An Efficient Algorithm for Partial Order Production.
SIAM J. Comput., 2010

Irreducible triangulations are small.
J. Comb. Theory, Ser. B, 2010

The Cops and Robber game on graphs with forbidden (induced) subgraphs.
Contributions Discret. Math., 2010

Hitting Diamonds and Growing Cacti.
Proceedings of the Integer Programming and Combinatorial Optimization, 2010

On a theorem of Sewell and Trotter.
Eur. J. Comb., 2009

Weighted graphs defining facets: A connection between stable set and linear ordering polytopes.
Discret. Optim., 2009

Minimum entropy orientations.
Oper. Res. Lett., 2008

Turán's theorem and <i>k</i>-connected graphs.
J. Graph Theory, 2008

Minimum entropy coloring.
J. Comb. Optim., 2008

Well-balanced orientations of mixed graphs.
Inf. Process. Lett., 2008

Tight Results on Minimum Entropy Set Cover.
Algorithmica, 2008

On a weighted generalization of alpha-critical graphs.
Electron. Notes Discret. Math., 2005