44 citations · 327 across the 39 of their papers we have counts for
26 papers · 1 filter
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…
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…
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…
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…
Spanning surfaces in 3-graphs
Agelos Georgakopoulos, John Haslegrave, Richard Montgomery +1
We prove a topological extension of Dirac's theorem suggested by Gowers in 2005: for any connected, closed surface , we show that any two-dimensional simplicial comple…
Forcing large tight components in 3-graphs
Agelos Georgakopoulos, John Haslegrave, Richard Montgomery
Any -vertex -graph with minimum codegree at least must have a spanning tight component, but immediately below this threshold it is possible for no tight…
Proof of a local antimagic conjecture
John Haslegrave
An antimagic labelling of a graph is a bijection such that the sums distinguish all vertices. A well-known conjecture of Ha…
Locating a robber with multiple probes
John Haslegrave, Richard A. B. Johnson, Sebastian Koch
We consider a game in which a cop searches for a moving robber on a connected graph using distance probes, which is a slight variation on one introduced by Seager. Carragher, Choi,…
An evasion game on a graph
John Haslegrave
This paper introduced a pursuit and evasion game to be played on a connected graph. One player moves invisibly around the graph, and the other player must guess his position. At ea…
Judicious partitions of uniform hypergraphs
John Haslegrave
The vertices of any graph with edges may be partitioned into two parts so that each part meets at least edges. Bollobás and Thomason conjectured that the vertice…
Majority dynamics with one nonconformist
John Haslegrave, Chris Cannings
We consider a system in which a group of agents represented by the vertices of a graph synchronously update their opinion based on that of their neighbours. If each agent adopts a…
Subdivisions in the Robber Locating Game
John Haslegrave, Richard A. B. Johnson, Sebastian Koch
We consider a game in which a cop searches for a moving robber on a graph using distance probes, which is a slight variation on one introduced by Seager. Carragher, Choi, Delcourt,…
Extremal results on average subtree density of series-reduced trees
John Haslegrave
Vince and Wang showed that the average subtree density of a series-reduced tree is between 1/2 and 3/4, answering a conjecture of Jamison. They ask under what conditions a sequence…