44 citations · 327 across the 39 of their papers we have counts for
41 papers
Stable cuts, NAC-colourings and flexible realisations of graphs
Katie Clinch, Dániel Garamvölgyi, John Haslegrave +3
A (2-dimensional) realisation of a graph is a pair , where maps the vertices of to . A realisation is flexible if it can be continuously deformed w…
Random triangulations of the d-sphere with minimum volume
Agelos Georgakopoulos, John Haslegrave, Joel Larsson Danielsson
We study a higher-dimensional analogue of the {Random Travelling Salesman Problem}: let the complete -dimensional simplicial complex on vertices be equipped with i…
Boundary rigidity of 3D CAT(0) cube complexes
John Haslegrave, Alex Scott, Youri Tamitegama +1
The boundary rigidity problem is a classical question from Riemannian geometry: if is a Riemannian manifold with smooth boundary, is the geometry of determined up to i…
Competing types in preferential attachment graphs with community structure
John Haslegrave, Jonathan Jordan, Mark Yarrow
We extend the two-type preferential attachment model of Antunović, Mossel and Rácz, where each new vertex takes its type according to a defined rule based on the types of its neigh…
Monitoring edge-geodetic sets: hardness and graph products
John Haslegrave
Foucaud, Krishna and Lekshmi recently introduced the concept of monitoring edge-geodetic sets in graphs, and a related graph invariant. These are sets of vertices such that the rem…
Tight Bounds on the Chromatic Edge Stability Index of Graphs
Saieed Akbari, John Haslegrave, Mehrbod Javadi +2
The chromatic edge stability index of a graph is the minimum number of edges whose removal results in a graph with smaller chromatic index. We give best-p…
When removing an independent set is optimal for reducing the chromatic number
Stijn Cambie, John Haslegrave, Ross J. Kang
How large must the chromatic number of a graph be, in terms of the graph's maximum degree, to ensure that the most efficient way to reduce the chromatic number by removing vertices…
Ramsey numbers of cycles versus general graphs
John Haslegrave, Joseph Hyde, Jaehoon Kim +1
The Ramsey number is the minimum number such that any -vertex graph either contains a copy of or its complement contains . Burr in 1981 proved a pleasingly g…
Determining triangulations and quadrangulations by boundary distances
John Haslegrave
We show that if a disc triangulation has all internal vertex degrees at least 6, then the full triangulation may be determined from the pairwise graph distance between boundary ver…
On the relationship between variable Wiener index and variable Szeged index
Stijn Cambie, John Haslegrave
We resolve two conjectures of Hriňáková, Knor and Škrekovski (2019) concerning the relationship between the variable Wiener index and variable Szeged index for a connected, non-com…
Crux and long cycles in graphs
John Haslegrave, Jie Hu, Jaehoon Kim +3
We introduce a notion of the \emph{crux} of a graph , measuring the order of a smallest dense subgraph in . This simple-looking notion leads to some generalisations of known…
Degrees in link graphs of regular graphs
Itai Benjamini, John Haslegrave
We analyse an extremal question on the degrees of the link graphs of a finite regular graph, that is, the subgraphs induced by non-trivial spheres. We show that if is -regul…
The number and average size of connected sets in graphs with degree constraints
John Haslegrave
The average size of connected vertex subsets of a connected graph generalises a much-studied parameter for subtrees of trees. For trees, the possible values of this parameter are c…
Sum index, difference index and exclusive sum number of graphs
John Haslegrave
We consider two recent conjectures of Harrington, Henninger-Voss, Karhadkar, Robinson and Wong concerning relationships between the sum index, difference index and exclusive sum nu…
The path minimises the average size of a connected induced subgraph
John Haslegrave
We prove that among all graphs of order n, the path uniquely minimises the average order of its connected induced subgraphs. This confirms a conjecture of Kroeker, Mol and Oellerma…
Extremal density for sparse minors and subdivisions
John Haslegrave, Jaehoon Kim, Hong Liu
We prove an asymptotically tight bound on the extremal density guaranteeing subdivisions of bounded-degree bipartite graphs with a mild separability condition. As corollaries, we a…
Time Dependent Biased Random Walks
John Haslegrave, Thomas Sauerwald, John Sylvester
We study the biased random walk where at each step of a random walk a "controller" can, with a certain small probability, move the walk to an arbitrary neighbour. This model was in…
Combinatorial universality in three-speed ballistic annihilation
John Haslegrave, Laurent Tournier
We consider a one-dimensional system of particles, moving at constant velocities chosen independently according to a symmetric distribution on , and annihilating upon…
Countable graphs are majority 3-choosable
John Haslegrave
The Unfriendly Partition Conjecture posits that every countable graph admits a 2-colouring in which for each vertex there are at least as many bichromatic edges containing that ver…
A time-invariant random graph with splitting events
Agelos Georgakopoulos, John Haslegrave
We introduce a process where a connected rooted multigraph evolves by splitting events on its vertices, occurring randomly in continuous time. When a vertex splits, its incoming ed…
The Power of Two Choices for Random Walks
Agelos Georgakopoulos, John Haslegrave, Thomas Sauerwald +1
We apply the power-of-two-choices paradigm to a random walk on a graph: rather than moving to a uniform random neighbour at each step, a controller is allowed to choose from two in…
Site percolation and isoperimetric inequalities for plane graphs
John Haslegrave, Christoforos Panagiotis
We use isoperimetric inequalities combined with a new technique to prove upper bounds for the site percolation threshold of plane graphs with given minimum degree conditions. In th…
Three-speed ballistic annihilation: phase transition and universality
John Haslegrave, Vladas Sidoravicius, Laurent Tournier
We consider ballistic annihilation, a model for chemical reactions first introduced in the 1980's physics literature. In this particle system, initial locations are given by a rene…
The ballistic annihilation threshold is positive
John Haslegrave
In the ballistic annihilation process, particles on the real line have independent speeds symmetrically distributed in and are annihilated by collisions. It is widely…