Abstract Halin’s well-known grid theorem states that a graph G with a thick end must contain a subdivision of the hexagonal half-grid. We obtain the following strengthening when G is vertex-transitive and locally finite. Either G is quasi-isometric to a tree (and therefore has no thick end), or it contains a subdivision of the full hexagonal grid.

In this paper, we consider the class 𝒞^d of sphere intersection graphs in R^d for d ≥ 2. We show that for each integer t, the class of all graphs in 𝒞^d that exclude K_{t,t} as a subgraph has strongly sublinear separators. We also prove that 𝒞^d has asymptotic dimension at most 2d+2.

Abstract Mohar recently adapted the classical game of Cops and Robber from graphs to metric spaces, thereby unifying previously studied pursuit-evasion games. He conjectured that finitely many cops can win on any compact geodesic metric space, and that their number can be upper-bounded in terms of the ranks of the homology groups when the space is a simplicial pseudo-manifold. We disprove these conjectures by constructing a metric on $$\mathbb {S}^3$$ S 3 with infinite cop number. More problems are raised than settled.

We analyse the following random walk process inspired by the power-of-two-choice paradigm: starting from a given vertex, at each step, unlike the simple random walk (SRW) that always moves to a randomly chosen neighbour, we have the choice between two uniformly and independently chosen neighbours. We call this process the choice random walk (CRW). We first prove that for any graph, there is a strategy for the CRW that visits any given vertex in expected time ?(|E|). Then we introduce a general tool that quantifies by how much the probability of a rare event in the simple random walk can be boosted under a suitable CRW strategy. We believe this result to be of independent interest, and apply it here to derive an almost optimal ?(n log log n) bound for the cover time of bounded-degree expanders. This tool also applies to so-called biased walks, and allows us to make progress towards a conjecture of Azar et al. [STOC 1992]. Finally, we prove the following dichotomy: computing an optimal strategy to minimise the hitting time of a vertex takes polynomial time, whereas computing one to minimise the cover time is NP-hard.

Fleischner's theorem says that the square of every 2-connected graph contains a Hamiltonian cycle. We present a proof resulting in an O(|E|) algorithm for producing a Hamiltonian cycle in the square G2 of a 2-connected graph G = (V, E). The previous best was O(|V|2) by Lau in 1980. More generally, we get an O(|E|) algorithm for producing a Hamiltonian path between any two prescribed vertices, and we get an O(|V|2) algorithm for producing cycles C3, C4, …, C|V| in G2 of lengths 3,4, …, |V|, respectively.

The aim of this paper is to clarify the relationship between Gromov-hyperbolicity and amenability for planar maps.