2025
Improved lower bounds on the maximum size of graphs with girth 5.
CoRR, August, 2025
A Caro-Wei Bound for Induced Linear Forests in Graphs.
SIAM J. Discret. Math., 2025
Discret. Math. Theor. Comput. Sci., 2025
Tight bound for the Erdős-Pósa property of tree minors.
Comb. Probab. Comput., 2025
Planar Graphs in Blowups of Fans.
Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms, 2025
Integer programs with nearly totally unimodular matrices: the cographic case.
Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms, 2025
2024
Neighborhood Complexity of Planar Graphs.
Comb., October, 2024
Tight Bound on Treedepth in Terms of Pathwidth and Longest Path.
Comb., April, 2024
Pathwidth Versus Cocircumference.
SIAM J. Discret. Math., March, 2024
The Excluded Tree Minor Theorem Revisited.
Comb. Probab. Comput., January, 2024
Product Structure Extension of the Alon-Seymour-Thomas Theorem.
SIAM J. Discret. Math., 2024
Erdős-Pósa property of cycles that are far apart.
CoRR, 2024
Integer programs with nearly totally unimodular matrices: the cographic case.
CoRR, 2024
Bounded-Degree Planar Graphs Do Not Have Bounded-Degree Product Structure.
Electron. J. Comb., 2024
Cliquewidth and Dimension.
Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, 2024
The Grid-Minor Theorem Revisited.
Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, 2024
2023
Treedepth vs Circumference.
Comb., August, 2023
Pathwidth vs cocircumference.
CoRR, 2023
Edge Separators for Graphs Excluding a Minor.
Electron. J. Comb., 2023
2022
Subgraph densities in a surface.
Comb. Probab. Comput., 2022
Improved Bounds for Weak Coloring Numbers.
Electron. J. Comb., 2022
2021
Unavoidable Minors for Graphs with Large ℓ <sub>p</sub>-Dimension.
Discret. Comput. Geom., 2021
Tight Bounds on the Clique Chromatic Number.
Electron. J. Comb., 2021
Smaller Extended Formulations for Spanning Tree Polytopes in Minor-closed Classes and Beyond.
Electron. J. Comb., 2021
Packing and Covering Balls in Graphs Excluding a Minor.
Comb., 2021
Approximating Pathwidth for Graphs of Small Treewidth.
Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, 2021
Integer programs with bounded subdeterminants and two nonzeros per row.
Proceedings of the 62nd IEEE Annual Symposium on Foundations of Computer Science, 2021
2020
Progress on the Adjacent Vertex Distinguishing Edge Coloring Conjecture.
SIAM J. Discret. Math., 2020
Minor-Closed Graph Classes with Bounded Layered Pathwidth.
SIAM J. Discret. Math., 2020
Erdös-Pósa from Ball Packing.
SIAM J. Discret. Math., 2020
Two lower bounds for p-centered colorings.
Discret. Math. Theor. Comput. Sci., 2020
Sparse universal graphs for planarity.
CoRR, 2020
Notes on Graph Product Structure Theory.
CoRR, 2020
Revisiting a Theorem by Folkman on Graph Colouring.
Electron. J. Comb., 2020
Seymour's Conjecture on 2-Connected Graphs of Large Pathwidth.
Comb., 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
Adjacency Labelling for Planar Graphs (and Beyond).
Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science, 2020
2019
Large independent sets in triangle-free cubic graphs: beyond planarity.
CoRR, 2019
Planar graphs have bounded nonrepetitive chromatic number.
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
Planar Graphs have Bounded Queue-Number.
Proceedings of the 60th IEEE Annual Symposium on Foundations of Computer Science, 2019
2018
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
Progress on the adjacent vertex distinguishing edge colouring conjecture.
CoRR, 2018
2017
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
Assortment Optimisation under a General Discrete Choice Model: A Tight Analysis of Revenue-Ordered Assortments.
Proceedings of the 2017 ACM Conference on Economics and Computation, 2017
2016
$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
Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2016
Improved Approximation Algorithms for Hitting 3-Vertex Paths.
Proceedings of the Integer Programming and Combinatorial Optimization, 2016
2015
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
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
2013
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 B, 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
2012
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
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
2011
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
Hitting and Harvesting Pumpkins.
Proceedings of the Algorithms - ESA 2011, 2011
2010
Irreducible triangulations are small.
J. Comb. Theory B, 2010
The Cops and Robber game on graphs with forbidden (induced) subgraphs.
Contributions Discret. Math., 2010
Sorting under partial information (without the ellipsoid algorithm).
Proceedings of the 42nd ACM Symposium on Theory of Computing, 2010
Hitting Diamonds and Growing Cacti.
Proceedings of the Integer Programming and Combinatorial Optimization, 2010
2009
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
The Stackelberg Minimum Spanning Tree Game on Planar and Bounded-Treewidth Graphs.
Proceedings of the Internet and Network Economics, 5th International Workshop, 2009
An efficient algorithm for partial order production.
Proceedings of the 41st Annual ACM Symposium on Theory of Computing, 2009
Minimum Entropy Combinatorial Optimization Problems.
Proceedings of the Mathematical Theory and Computational Practice, 2009
2008
Minimum entropy orientations.
Oper. Res. Lett., 2008
Turán's theorem and <i>k</i>-connected graphs.
J. Graph Theory, 2008
Well-balanced orientations of mixed graphs.
Inf. Process. Lett., 2008
2007
The Stackelberg Minimum Spanning Tree Game.
Proceedings of the Algorithms and Data Structures, 10th International Workshop, 2007
2006
Tight Results on Minimum Entropy Set Cover.
Proceedings of the Approximation, 2006
2005
On a weighted generalization of alpha-critical graphs.
Electron. Notes Discret. Math., 2005
Minimum Entropy Coloring.
Proceedings of the Algorithms and Computation, 16th International Symposium, 2005
