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.
Explicit bounds for graph minors / Geelen, J.; Huynh, T.; Bruce Richter, R.. - In: JOURNAL OF COMBINATORIAL THEORY. - ISSN 0095-8956. - 132:(2018), pp. 80-106. [10.1016/j.jctb.2018.03.004]
Explicit bounds for graph minors
Huynh T.;
2018
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.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
