We wish to bring attention to a natural but slightly hidden problem, posed by Erdös and Nešetřil in the late 1980s, an edge version of the degree--diameter problem. Our main result is that, for any graph of maximum degree $\Delta$ with more than $1.5 \Delta^t$ edges, its line graph must have diameter larger than $t$. In the case where the graph contains no cycle of length $2t+1$, we can improve the bound on the number of edges to one that is exact for $t\in\{1,2,3,4,6\}$. In the case $\Delta=3$ and $t=3$, we obtain an exact bound. Our results also have implications for the related problem of bounding the distance-$t$ chromatic index, $t>2$; in particular, for this, we obtain an upper bound of $1.941\Delta^t$ for graphs of large enough maximum degree $\Delta$, markedly improving on earlier bounds for this parameter.

A classic theorem of Erdös and Pósa [ Canad. J. Math., 17 (1965), pp. 347--352] states that every graph has either $k$ vertex-disjoint cycles or a set of $O(k \log k)$ vertices meeting all its cycles. While the standard proof revolves around finding a large “frame” in the graph (a subdivision of a large cubic graph), an alternative way of proving this theorem is to use a ball packing argument of Kühn and Osthus [ Random Structures Algorithms, 22 (2003), pp. 213--225] and Diestel and Rempel [ Combinatorica, 25 (2005), pp. 111--116]. In this paper, we argue that the latter approach is particularly well suited for studying edge variants of the Erdös--Pósa theorem. As an illustration, we give a short proof of a theorem of Bruhn, Heinlein, and Joos [ Combinatorica, 39 (2019), pp. 1--36] that cycles of length at least $\ell$ have the so-called edge-Erdös--Pósa property. More precisely, we show that every graph $G$ contains either $k$ edge-disjoint cycles of length at least $\ell$ or an edge set $F$ of size $O(k\ell \cdot \log (k\ell))$ such that $G-F$ has no cycle of length at least $\ell$. For fixed $\ell$, this improves on the previously best known bound of $O(k^2 \log k +k\ell)$.

Let H be a planar graph. By a classical result of Robertson and Seymour, there is a function f : ℕ → ℝ such that for all k ∊ ℕ and all graphs G, either G contains k vertex-disjoint subgraphs each containing H as a minor, or there is a subset X of at most f(k) vertices such that G–X has no H-minor. We prove that this remains true with f(k) = ck log k for some constant c = c(H). This bound is best possible, up to the value of c, and improves upon a recent result of Chekuri and Chuzhoy [STOC 2013], who established this with f(k) = ck logd k for some universal constant d. The proof is constructive and yields a polynomial-time O(log OPT)-approximation algorithm for packing subgraphs containing an H-minor.

A Jordan region is a subset of the plane that is homeomorphic to a closed disk. Consider a family $\mathcal{F}$ of Jordan regions whose interiors are pairwise disjoint, and such that any two Jordan regions intersect in at most one point. If any point of the plane is contained in at most $k$ elements of $\mathcal{F}$ (with $k$ sufficiently large), then we show that the elements of $\mathcal{F}$ can be colored with at most k+1 colors so that intersecting Jordan regions are assigned distinct colors. This is best possible and answers a question raised by Reed and Shepherd in 1996. As a simple corollary, we also obtain a positive answer to a problem of Hlin\vený (1998) on the chromatic number of contact systems of strings. We also investigate the chromatic number of families of touching Jordan curves. This can be used to bound the ratio between the maximum number of vertex-disjoint directed cycles in a planar digraph, and its fractional counterpart.