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

Packing topological minors half-integrally

Formale Metadaten

Titel
Packing topological minors half-integrally
Serientitel
Anzahl der Teile
24
Autor
Lizenz
CC-Namensnennung - keine kommerzielle Nutzung - keine Bearbeitung 4.0 International:
Sie dürfen das Werk bzw. den Inhalt in unveränderter Form zu jedem legalen und nicht-kommerziellen Zweck nutzen, vervielfältigen, verbreiten und öffentlich zugänglich machen, sofern Sie den Namen des Autors/Rechteinhabers in der von ihm festgelegten Weise nennen.
Identifikatoren
Herausgeber
Erscheinungsjahr
Sprache

Inhaltliche Metadaten

Fachgebiet
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\).
Schlagwörter