Explicit bounds for graph minors

Jim Geelen, Tony Huynh, R. Bruce Richter

Research output: Contribution to journalArticleResearchpeer-review

1 Citation (Scopus)

Abstract

Let Σ be a surface with boundary bd(Σ), L be a collection of k disjoint bd(Σ)-paths in Σ, and P be a non-separating bd(Σ)-path in Σ. We prove that there is a homeomorphism ϕ:Σ→Σ that fixes each point of bd(Σ) and such that ϕ(L) meets P at most 2k times. With this theorem, we derive explicit constants in the graph minor algorithms of Robertson and Seymour (1995) [10]. We reprove a result concerning redundant vertices for graphs on surfaces, but with explicit bounds. That is, we prove that there exists a computable integer t:=t(Σ,k) such that if v is a ‘t-protected’ vertex in a surface Σ, then v is redundant with respect to any k-linkage.

Original languageEnglish
Pages (from-to)80-106
Number of pages27
JournalJournal of Combinatorial Theory. Series B
Volume132
DOIs
Publication statusPublished - 1 Sep 2018
Externally publishedYes

Keywords

  • Graphs
  • Linkages
  • Minors
  • Surfaces

Cite this