2024
A Note on the Gyárfás-Sumner Conjecture.
Graphs Comb., April, 2024
Pure Pairs. IX. Transversal Trees.
SIAM J. Discret. Math., March, 2024
Invertibility of Digraphs and Tournaments.
SIAM J. Discret. Math., March, 2024
On a problem of El-Zahar and Erdős.
J. Comb. Theory, Ser. B, March, 2024
Polynomial bounds for chromatic number. V. Excluding a tree of radius two and a complete multipartite graph.
J. Comb. Theory, Ser. B, January, 2024
Induced paths in graphs without anticomplete cycles.
J. Comb. Theory, Ser. B, January, 2024
Bipartite graphs with no <i>K</i><sub>6</sub> minor.
J. Comb. Theory, Ser. B, January, 2024
Pure pairs. X. Tournaments and the strong Erdős-Hajnal property.
Eur. J. Comb., January, 2024
Induced Subgraphs of Induced Subgraphs of Large Chromatic Number.
Comb., 2024
2023
Polynomial bounds for chromatic number VII. Disjoint holes.
J. Graph Theory, November, 2023
Strengthening Rödl's theorem.
J. Comb. Theory, Ser. B, November, 2023
Polynomial Bounds for Chromatic Number. IV: A Near-polynomial Bound for Excluding the Five-vertex Path.
Comb., October, 2023
Best-response dynamics, playing sequences, and convergence to equilibrium in random games.
Int. J. Game Theory, September, 2023
Pure pairs. VII. Homogeneous submatrices in 0/1-matrices with a forbidden submatrix.
J. Comb. Theory, Ser. B, July, 2023
Pure pairs. IV. Trees in bipartite graphs.
J. Comb. Theory, Ser. B, July, 2023
Decomposing Random Permutations into Order-Isomorphic Subpermutations.
SIAM J. Discret. Math., June, 2023
Pure Pairs. V. Excluding Some Long Subdivision.
Comb., June, 2023
Counting partitions of G n , 1 / 2 $$ {G}_{n,1/2} $$ with degree congruence conditions.
Random Struct. Algorithms, May, 2023
Polynomial bounds for chromatic number VI. Adding a four-vertex path.
Eur. J. Comb., May, 2023
Clustered colouring of graph classes with bounded treedepth or pathwidth.
Comb. Probab. Comput., January, 2023
Polynomial bounds for chromatic number. I. Excluding a biclique and an induced tree.
J. Graph Theory, 2023
Superpolynomial smoothed complexity of 3-FLIP in Local Max-Cut.
CoRR, 2023
Game Connectivity and Adaptive Dynamics.
CoRR, 2023
Balancing Connected Colourings of Graphs.
Electron. J. Comb., 2023
2022
Pure Pairs VI: Excluding an Ordered Tree.
SIAM J. Discret. Math., 2022
A Note on Infinite Antichain Density.
SIAM J. Discret. Math., 2022
Shotgun reconstruction in the hypercube.
Random Struct. Algorithms, 2022
Polynomial bounds for chromatic number. III. Excluding a double star.
J. Graph Theory, 2022
Polynomial bounds for chromatic number II: Excluding a star-forest.
J. Graph Theory, 2022
Reconstructing the degree sequence of a sparse graph from a partial deck.
J. Comb. Theory, Ser. B, 2022
Shotgun assembly of random graphs.
CoRR, 2022
A multidimensional Ramsey Theorem.
CoRR, 2022
Concatenating Bipartite Graphs.
Electron. J. Comb., 2022
2021
Finding a Shortest Odd Hole.
ACM Trans. Algorithms, 2021
The component structure of dense random subgraphs of the hypercube.
Random Struct. Algorithms, 2021
Size reconstructibility of graphs.
J. Graph Theory, 2021
Maximising the number of cycles in graphs with forbidden subgraphs.
J. Comb. Theory, Ser. B, 2021
Induced subgraphs of graphs with large chromatic number. V. Chandeliers and strings.
J. Comb. Theory, Ser. B, 2021
A note on simplicial cliques.
Discret. Math., 2021
Lipschitz bijections between boolean functions.
Comb. Probab. Comput., 2021
Powers of paths in tournaments.
Comb. Probab. Comput., 2021
Monochromatic Components in Edge-Coloured Graphs with Large Minimum Degree.
Electron. J. Comb., 2021
Pure Pairs. II. Excluding All Subdivisions of A Graph.
Comb., 2021
Detecting a Long Odd Hole.
Comb., 2021
Optimal labelling schemes for adjacency, comparability, and reachability.
Proceedings of the STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, 2021
Active clustering for labeling training data.
Proceedings of the Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, 2021
2020
A survey of χ-boundedness.
J. Graph Theory, 2020
Pure pairs. III. Sparse graphs with no polynomial-sized anticomplete pairs.
J. Graph Theory, 2020
Induced subgraphs of graphs with large chromatic number. VI. Banana trees.
J. Comb. Theory, Ser. B, 2020
Induced subgraphs of graphs with large chromatic number. VII. Gyárfás' complementation conjecture.
J. Comb. Theory, Ser. B, 2020
Partitioning the vertices of a torus into isomorphic subgraphs.
J. Comb. Theory, Ser. A, 2020
Induced subgraphs of graphs with large chromatic number. VIII. Long odd holes.
J. Comb. Theory, Ser. B, 2020
Induced subgraphs of graphs with large chromatic number. XIII. New brooms.
Eur. J. Comb., 2020
Asymptotic Dimension of Minor-Closed Families and Assouad-Nagata Dimension of Surfaces.
CoRR, 2020
2019
Bad news for chordal partitions.
J. Graph Theory, 2019
Maximising -colourings of graphs.
J. Graph Theory, 2019
Induced subgraphs of graphs with large chromatic number. XII. Distant stars.
J. Graph Theory, 2019
Near-domination in graphs.
J. Comb. Theory, Ser. A, 2019
Disjoint paths in unions of tournaments.
J. Comb. Theory, Ser. B, 2019
Induced subgraphs of graphs with large chromatic number. XI. Orientations.
Eur. J. Comb., 2019
H-colouring Pt-free graphs in subexponential time.
Discret. Appl. Math., 2019
Induced Subgraphs of Graphs With Large Chromatic Number. X. Holes of Specific Residue.
Comb., 2019
Clustered Colouring in Minor-Closed Classes.
Comb., 2019
Towards Erdős-Hajnal for Graphs with No 5-Hole.
Comb., 2019
2018
Induced subgraphs of graphs with large chromatic number. IV. Consecutive holes.
J. Comb. Theory, Ser. B, 2018
Supersaturation in posets and applications involving the container method.
J. Comb. Theory, Ser. A, 2018
Stability results for graphs with a critical edge.
Eur. J. Comb., 2018
How unproportional must a graph be?
Eur. J. Comb., 2018
Better bounds for poset dimension and boxicity.
CoRR, 2018
H-colouring P<sub>t</sub>-free graphs in subexponential time.
CoRR, 2018
2017
Uniform multicommodity flows in the hypercube with random edge-capacities.
Random Struct. Algorithms, 2017
Packing random graphs and hypergraphs.
Random Struct. Algorithms, 2017
On Lower Bounds for the Matching Number of Subcubic Graphs.
J. Graph Theory, 2017
Maximising the number of induced cycles in a graph.
J. Comb. Theory, Ser. B, 2017
Saturation in the Hypercube and Bootstrap Percolation.
Comb. Probab. Comput., 2017
Induced Subgraphs of Graphs with Large Chromatic Number IX: Rainbow Paths.
Electron. J. Comb., 2017
A Note on Intersecting Hypergraphs with Large Cover Number.
Electron. J. Comb., 2017
Induced Subgraphs of Graphs with Large Chromatic Number. III. Long Holes.
Comb., 2017
2016
Induced subgraphs of graphs with large chromatic number. I. Odd holes.
J. Comb. Theory, Ser. B, 2016
Induced subgraphs of graphs with large chromatic number. II. Three steps towards Gyárfás' conjectures.
J. Comb. Theory, Ser. B, 2016
J. Comb. Theory, Ser. B, 2016
The parameterised complexity of list problems on graphs of bounded treewidth.
Inf. Comput., 2016
Random graphs from a block-stable class.
Eur. J. Comb., 2016
Feedback from nature: simple randomised distributed algorithms for maximal independent set selection and greedy colouring.
Distributed Comput., 2016
2015
Intersections of hypergraphs.
J. Comb. Theory, Ser. B, 2015
Intersections of random hypergraphs and tournaments.
Eur. J. Comb., 2015
Disjoint induced subgraphs of the same order and size.
Eur. J. Comb., 2015
2014
Hypergraphs of Bounded Disjointness.
SIAM J. Discret. Math., 2014
For most graphs <i>H</i>, most <i>H</i>-free graphs have a linear homogeneous set.
Random Struct. Algorithms, 2014
Spanning Trees and the Complexity of Flood-Filling Games.
Theory Comput. Syst., 2014
Excluding pairs of graphs.
J. Comb. Theory, Ser. B, 2014
Uniform multicommodity flow in the hypercube with random edge capacities.
CoRR, 2014
On Saturated k-Sperner Systems.
Electron. J. Comb., 2014
2013
The complexity of Free-Flood-It on 2×n boards.
Theor. Comput. Sci., 2013
Cover-Decomposition and Polychromatic Numbers.
SIAM J. Discret. Math., 2013
A counterexample to a conjecture of Schwartz.
Soc. Choice Welf., 2013
Substitution and χ-boundedness.
J. Comb. Theory, Ser. B, 2013
Tournaments and colouring.
J. Comb. Theory, Ser. B, 2013
Feedback from nature: an optimal distributed algorithm for maximal independent set selection.
Proceedings of the ACM Symposium on Principles of Distributed Computing, 2013
2012
The minimal covering set in large tournaments.
Soc. Choice Welf., 2012
Excluding Induced Subdivisions of the Bull and Related Graphs.
J. Graph Theory, 2012
The complexity of flood-filling games on graphs.
Discret. Appl. Math., 2012
Monochromatic Cycles in 2-Coloured Graphs.
Comb. Probab. Comput., 2012
2011
A Bound for the Cops and Robbers Problem.
SIAM J. Discret. Math., 2011
Szemerédi's Regularity Lemma for Matrices and Sparse Graphs.
Comb. Probab. Comput., 2011
The complexity of Free-Flood-It on 2xn boards
CoRR, 2011
2010
Max k-cut and judicious k-partitions.
Discret. Math., 2010
Structure of random r-SAT below the pure literal threshold
CoRR, 2010
2009
Polynomial constraint satisfaction problems, graph bisection, and the Ising partition function.
ACM Trans. Algorithms, 2009
Uniform multicommodity flow through the complete graph with random edge-capacities.
Oper. Res. Lett., 2009
2007
Maximum directed cuts in acyclic digraphs.
J. Graph Theory, 2007
Separating systems and oriented graphs of diameter two.
J. Comb. Theory, Ser. B, 2007
Infinite Locally Random Graphs.
Internet Math., 2007
Linear-programming design and analysis of fast algorithms for Max 2-CSP.
Discret. Optim., 2007
Computational complexity of some restricted instances of 3-SAT.
Discret. Appl. Math., 2007
2006
Reconstructing under Group Actions.
Graphs Comb., 2006
Solving Sparse Random Instances of Max Cut and Max 2-CSP in Linear Expected Time.
Comb. Probab. Comput., 2006
On Dependency Graphs and the Lattice Gas.
Comb. Probab. Comput., 2006
Linear-programming design and analysis of fast algorithms for Max 2-Sat and Max 2-CSP
CoRR, 2006
Polynomial Constraint Satisfaction: A Framework for Counting and Sampling CSPs and Other Problems
CoRR, 2006
An LP-Designed Algorithm for Constraint Satisfaction.
Proceedings of the Algorithms, 2006
2005
Judicious partitions and related problems.
Proceedings of the Surveys in Combinatorics, 2005
2004
Judicious partitions of bounded-degree graphs.
J. Graph Theory, 2004
Computational Complexity of Some Restricted Instances of 3SAT
Electron. Colloquium Comput. Complex., 2004
Topics in Graph Automorphisms and Reconstruction by Josef Lauri and Raffaele Scapellato, Cambridge University Press, 2003, 172 pp.
Comb. Probab. Comput., 2004
Max Cut for Random Graphs with a Planted Partition.
Comb. Probab. Comput., 2004
2003
Finite Subsets of the Plane are 18-Reconstructible.
SIAM J. Discret. Math., 2003
Approximation Hardness of Short Symmetric Instances of MAX-3SAT.
Electron. Colloquium Comput. Complex., 2003
Approximation Hardness and Satisfiability of Bounded Occurrence Instances of SAT
Electron. Colloquium Comput. Complex., 2003
Special Issue on Ramsey Theory.
Comb. Probab. Comput., 2003
Faster Algorithms for MAX CUT and MAX CSP, with Polynomial Expected Time for Sparse Instances.
Proceedings of the Approximation, 2003
2002
Problems and results on judicious partitions.
Random Struct. Algorithms, 2002
A Note on Cycle Lengths in Graphs.
Graphs Comb., 2002
2001
On Induced Subgraphs with All Degrees Odd.
Graphs Comb., 2001
Alternating Knot Diagrams, Euler Circuits and the Interlace Polynomial.
Eur. J. Comb., 2001
2000
Subdivisions of Transitive Tournaments.
Eur. J. Comb., 2000
Judicious Partitions of 3-uniform Hypergraphs.
Eur. J. Comb., 2000
1999
Induced Cycles and Chromatic Number.
J. Comb. Theory, Ser. B, 1999
Another Simple Proof of a Theorem of Milner.
J. Comb. Theory, Ser. A, 1999
Reconstructing Subsets of Reals.
Electron. J. Comb., 1999
Exact Bounds for Judicious Partitions of Graphs.
Comb., 1999
1998
Reconstructing Subsets of Z<sub>n</sub>.
J. Comb. Theory, Ser. A, 1998
1997
Induced trees in graphs of large chromatic number.
J. Graph Theory, 1997
Judicious Partitions of Hypergraphs.
J. Comb. Theory, Ser. A, 1997
On graph decompositions modulo k.
Discret. Math., 1997
Reconstructing sequences.
Discret. Math., 1997
Independent sets and repeated degrees.
Discret. Math., 1997
All trees contain a large induced subgraph having all degrees 1 (mod k).
Discret. Math., 1997
Better Bounds for Perpetual Gossiping.
Discret. Appl. Math., 1997
1996
A Proof of a Conjecture of Bondy Concerning Paths in Weighted Digraphs.
J. Comb. Theory, Ser. B, 1996
1995
Every tree contains a large induced subgraph with all degrees odd.
Discret. Math., 1995
1992
Large Induced Subgraphs with All Degrees Odd.
Comb. Probab. Comput., 1992
