Packing and covering immersions in 4-edge-connected graphs (Q1984514)

The paper under review studies the edge variant Erdős-Pósa property. Given a set of graphs \(\mathcal{F}\) and a graph \(G\). The packing number is the maximum number of mutually disjoint subgraphs of \(G\) each isomorphic to a member of \(\mathcal{F}\), and the covering number is the minimum number of vertices that are required to meet all such subgraphs. Thus the covering number is naturally an upper bound of the packing number. The Erdős-Pósa property is motivated by the question: when can the covering number be bounded by a function of the packing number from above? For a set of graphs \(\mathcal{F}\), \(\mathcal{F}\) is said to have the Erdős-Pósa property if for every integer \(k\), there exists a number \(f(k)\) such that for every graph \(G\), either \(G\) contains \(k\) disjoint subgraphs each isomorphic to a member of \(F\) (i.e. the packing number of \(G\) is at least \(k\)), or there exists \(Z\subseteq V (G)\) with \(|Z| \le f(k)\) such that \(G - Z\) does not contain a subgraph isomorphic to a member of \(\mathcal{F}\) (i.e. the covering number of \(G\) is at most \(f(k)\)). \textit{P. Erdős} and \textit{L. Pósa} [Can. J. Math. 17, 347--352 (1965; Zbl 0129.39904)] proved that the set of cycles has the Erdős-Pósa property. \textit{N. Robertson} and \textit{P. D. Seymour} [J. Comb. Theory, Ser. B 41, 92--114 (1986; Zbl 0598.05055)] proved a more general result in terms of minor. A graph is a minor of another graph if the former can be obtained from a subgraph of the latter by contracting edges. Robertson and Seymour proved that \(\mathcal{M}(H)\), the set of graphs containing \(H\) as a minor, has the Erdős-Pósa property if and only if \(H\) is planar. The concept of minor can be turned into the concept of topological minor. A graph is said to be a topological minor of another graph if the former can be obtained from a subgraph of the latter by repeatedly contracting edges incident with at least one vertex of degree two. Further, if we formally define the concept of topological minor in terms of mappings between vertex sets and edge sets of the two graphs involved, we can change it into an ``edge-disjoint'' version, and have the concept of immersion. Let \(H\) and \(G\) be graphs. An \(H\)-immersion in \(G\) is a pair of functions \(\Pi = (\pi_V , \pi_E )\) such that \par i) \(\pi_V\) is an injection from \(V(H)\) to \(V(G)\). \par ii) \(\pi_E\) maps \(E(H)\) to the set of subgraphs of \(G\) such that for every edge \(e\) of \(H\), if \(e\) has distinct ends \(x\) and \(y\), then \(\pi_E(e)\) is a path with ends \(\pi_V(x)\) and \(\pi_V(y)\), and if \(e\) is the loop with end \(v\), then \(\pi_E(e)\) is a cycle containing \(\pi_V(v)\). \par iii) If \(e_1\), \(e_2\) are distinct edges of \(H\), then \(\pi_E(e_1)\) and \(\pi_E(e_2)\) are edge-disjoint. A set \(\mathcal{F}\) of graphs is said to have the edge-variant of the Erdős-Pósa property if for every integer \(k\), there exists an integer \(f(k)\) such that for every graph \(G\), either \(G\) contains \(k\) edge-disjoint subgraphs each isomorphic to a member of \(F\), or there exists \(Z \subseteq E(G)\) with \(|Z| \le f(k)\) such that \(G - Z\) has no subgraph isomorphic to a member of \(\mathcal{F}\). One direction of this topic is that, for a family of graphs which does not have (the edge-variant of) the Erdős-Pósa property, it possibly has this property if we restrict the host graphs to be members of a smaller class of graphs. The main result of this paper says that if the host graph is 4-edge-connected, then the graph that contains \(H\) as an immersion has the edge-variant of the Erdős-Pósa property, for every graph \(H\). Theorem. For every graph \(H\), there exists a function \(f: \mathbb{N} \rightarrow \mathbb{N}\) such that for every graph G whose every component is 4-edge-connected and for every positive integer \(k\), either \(G\) contains \(k\) edge-disjoint subgraphs each containing \(H\) as an immersion, or there exists \(Z \subseteq E(G)\) with \(|Z| \le f(k)\) such that \(G - Z\) has no H-immersion. Another result of this paper is about the half-integral packing problem. For every loopless graph \(H\), an \(H\)-half-integral immersion in \(G\) is a pair of functions \((\pi_V, \pi_E)\) such that \par i) \(\pi_V\) is an injection from \(V (H)\) to \(V (G)\). \par ii) \(\pi_E\) maps every edge \(e\) with ends \(u\), \(v\) of \(H\) to a path in \(G\) from \(\pi_V (u)\) to \(\pi_V (v)\). \par iii) For every edge \(e\) of \(G\), there exist at most two edges \(e_1\) , \(e_2\) of \(H\) such that \(e \in \pi_E (e_1 )\) and \(e \in \pi_E (e_2 )\). The edge variant of Erdős-Pósa property holds for the set of graphs containing \(H\) as an half-integral immersion for all graphs \(H\), without the restriction of 4-edge-connectedness on the host graphs. Theorem. For every loopless graph \(H\), there exists a function \(f : \mathbb{N} \rightarrow \mathbb{N}\) such that for every graph \(G\) and for every positive integer \(k\), either 1. \(G\) contains \(k\) \(H\)-half-integral immersions \((\pi_V^{(1)}, \pi_E^{(1)})\), \(\dots\), \((\pi_V^{(k)}, \pi_E^{(k)})\) such that for every edge \(e\) of \(G\), there exist at most two pairs \((i, e^\prime )\) with \(1 \le i \le k\) and \(e' \in E(H)\) such that \(e \in \pi_E^{(i)}(e^\prime)\), or 2. there exists \(Z \subseteq E(G)\) with \(|Z| \le f(k)\) such that \(G - Z\) has no \(H\)-half-integral immersion.