A single exponential bound for the redundant vertex Theorem on surfaces

2013/09/30 by Frédéric Mazoit, Mazoit, Frédéric · 1 citation
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #Limits and Structures in Graph Theory #math.CO

paper · pdf · doi:10.48550/arxiv.1309.7820

arxiv created 2013/09/30 · openalex publication_date 2013/09/30 · arxiv updated 2013/10/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Let s1, t1,. . . sk, tk be vertices in a graph G embedded on a surface σof genus g. A vertex v of G is "redundant" if there exist k vertex disjoint paths linking si and ti (1 \lequal i \lequal k) in G if and only if such paths also exist in G - v. Robertson and Seymour proved in Graph Minors VII that if v is "far" from the vertices si and tj and v is surrounded in a planar part of σby l(g, k) disjoint cycles, then v is redundant. Unfortunately, their proof of the existence of l(g, k) is not constructive. In this paper, we give an explicit single exponential bound in g and k.

Cited by

• Quickly excluding an annotated planar graph

Related

• Explicit bounds for graph minors
• Irrelevant Vertices for the Planar Disjoint Paths Problem
• A Heawood-type result for the algebraic connectivity of graphs on surfaces
• An Erdős-Pósa theorem for cycles and faces of distinct lengths
• A quasi-polynomial bound for the minimal excluded minors for a surface