We're sorry but this page doesn't work properly without JavaScript enabled. Please enable it to continue.
Feedback

Packing topological minors half-integrally

Formal Metadata

Title
Packing topological minors half-integrally
Title of Series
Number of Parts
24
Author
License
CC Attribution - NonCommercial - NoDerivatives 4.0 International:
You are free to use, copy, distribute and transmit the work or content in unchanged form for any legal and non-commercial purpose as long as the work is attributed to the author in the manner specified by the author or licensor.
Identifiers
Publisher
Release Date
Language

Content Metadata

Subject Area
Genre
Abstract
The packing problem and the covering problem are two general optimization problems that form a pair of dual integer programming problems. Fix a family \(F\) of graphs, the packing problem asks for the maximum number of disjoint subgraphs of the input graph \(G\) where each is isomorphic to a member of \(F\), and the covering problem asks for the minimum number of vertices of \(G\) required to intersect all such subgraphs. We say \(F\) has the Erdos-Posa property if the solutions of these two problems with respect to \(F\) can be bounded in terms of each other. It is well-known that if \(H\) is a graph such that the set of \(H\) minors has the Erdos-Posa property, then \(H\) must be planar. Thomas conjectured that the planarity is not required if half-integral solutions of the packing problem are allowed. In other words, he conjectured that for every graph \(H\), there exists a function \(f\) such that for every graph \(G\), either \(G\) contains \(k\) subgraphs where each of them is an \(H\) minor such that every vertex of \(G\) is contained in at most two of those subgraphs, or there exists a set of at most \(f(k)\) vertices intersecting all \(H\) minors in \(G\). In this talk, we prove that the same statement holds for topological minors. It is a stronger statement that easily implies Thomas' conjecture. Namely, we prove that for every graph \(H\), there exists a function \(f\) such that for every graph \(G\), either \(G\) contains \(k\) subdivisions of \(H\) such that every vertex of \(G\) is contained in at most two of them, or there exists a set of at most \(f(k)\) vertices intersecting all subdivisions of \(H\) in \(G\).
Keywords