2024/06/24 by Christophe Paul, Paul, Christophe, Evangelos Protopapas +5
Mathematics · #05C10 #05C75 #05C83 #05C85 #68R10 #Advanced Harmonic Analysis Research #Algebraic Geometry and Number Theory #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #G.2.2 #Geometric Analysis and Curvature Flows
paper · pdf · doi:10.48550/arxiv.2406.16647
openalex publication_date 2024/06/24 · openalex created_date 2024/06/26 · openalex updated_date 2026/07/28
In 1986 Robertson and Seymour proved a generalization of the seminal result of Erdős and Pósa on the duality of packing and covering cycles: A graph has the Erdős-Pósa property for minors if and only if it is planar. In particular, for every non-planar graph H they gave examples showing that the Erdős-Pósa property does not hold for H. Recently, Liu confirmed a conjecture of Thomas and showed that every graph has the half-integral Erdős-Pósa property for minors. Liu's proof is non-constructive and to this date, with the exception of a small number of examples, no constructive proof is known. In this paper, we initiate the delineation of the half-integrality of the Erdős-Pósa property for minors. We conjecture that for every graph H, there exists a unique (up to a suitable equivalence relation) graph parameter \textsfEPH such that H has the Erdős-Pósa property in a minor-closed graph class G if and only if sup\\textsfEPH(G) | G\inG\ is finite. We prove this conjecture for the class H of Kuratowski-connected shallow-vortex minors by showing that, for every non-planar H\inH, the parameter \sf EPH(G) is precisely the maximum order of a Robertson-Seymour counterexample to the Erdős-Pósa property of H which can be found as a minor in G. Our results are constructive and imply, for the first time, parameterized algorithms that find either a packing, or a cover, or one of the Robertson-Seymour counterexamples, certifying the existence of a half-integral packing for the graphs in H.