Packing and covering balls in graphs excluding a minor (Q2043760): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
Removed claim: reviewed by (P1447): Item:Q590772 |
||
Property / reviewed by | |||
Property / reviewed by: David B. Penman / rank | |||
Revision as of 23:40, 19 February 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Packing and covering balls in graphs excluding a minor |
scientific article |
Statements
Packing and covering balls in graphs excluding a minor (English)
0 references
3 August 2021
0 references
The paper under review considers graphs with no \(K_{t}\)-minor. The main result proved is that given \(t\geq 1\), there is a constant \(c_{t}\) such that for any \(K_{t}\)-free graph \(G\) and every set of balls in \(G\), the minimum size of a set of vertices intersecting all the balls is at most \(c_{t}\) times the size of a largest collection of disjoint balls. Here as usual the ball of radius \(r\) centred at a vertex \(v\) in a graph is the set of all vertices at graph distance at most \(r\) from \(v\) in the graph. In the language of hypergraph theory, this states that the transversal number of the hypergraph \(\mathcal{H}\) with vertex set \(V(G)\) and hyperedges the set \(S\) of balls has transversal number (smallest size of a set of vertices intersecting all edges), \(\tau(\mathcal{H})\) at most \(c_{t}\) times the matching number \(\mu(\mathcal{H})\). (Note that the inequality \(\tau(\mathcal{H})\geq \nu(\mathcal{H})\) is immediate). It is important to understand that \(c_{t}\) does not depend on the radii of the balls. Of course the result applies in particular to planar graphs as planarity implies no \(K_{5}\)-minor. The proofs use the Erdős-Pósa property of the ball hypergraphs and results on their Vapnik-Chervonenkis dimension. The proof of the main result is constructive and could be turned into an efficient algorithm to find a transversal.
0 references
packing
0 references
covering
0 references