Can I read A single exponential bound for the redundant vertex Theorem on surfaces on EtoBox?

A single exponential bound for the redundant vertex Theorem on surfaces by Mazoit, Frédéric is a scholarly article available to read on EtoBox.

What is A single exponential bound for the redundant vertex Theorem on surfaces about?

Let s1, t1,. . . sk, tk be vertices in a graph G embedded on a surface \sigma 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 \sigma 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.

Author

Mazoit, Frédéric

Published

2013

Language

EN