I have a question about the number of different ways to separate a terminal vertex from labeled vertex sets in a simple graph. There is a bound on this number that I am interested in. I have succeeded in proving a suitable upper bound, and am now wondering whether any research on similar topics has been done before; it would be nice if I could refer to some source for the claimed bound rather than proving it from scratch. Here are the details.
Let $G$ be a finite simple connected undirected graph with some distinguished terminal vertex $t$.Let $X$ be a finite set of labels; each vertex in $V(G) \setminus \{t\}$ can be labeled with arbitrarily many labels from the set $X$, which we represent by a labelling function $f : V(G) \setminus \{t\} \to 2^X$ which maps to a vertex $v$ the set of labels $f(v)$ that the vertex has. Consider a subset of vertices $S \subseteq V(G) \setminus \{t\}$, and call this a separator. Let $G - S$ denote the graph $G$ after removing all vertices of $S$. We say that $S$ separates the terminal $t$ from a label $x \in X$ if there is no path in $G - S$ from $t$ to a vertex with label $x$, i.e. a vertex $v$ with $x \in f(v)$. The set of labels separated by $S$ is then simply the set of all labels $x \in X$ for which $S$ separates $t$ from $x$.
Now fix some integer $c > 0$, and look at the different label sets which are separated from t by a size-c separator: $C_c :=$ { $X' \subseteq X$ | there is a separator $S$ of size $c$ which separates $X'$ from $t$}
Now my claim is that $|C_c| \leq |X|^{(g(c))}$ for some appropriate function $g$, or equivalently that for fixed separator size $c$ the number of different ways to separate $t$ from the labels is polynomial in the number of labels. Is this known? Has there been any work related to this, or is there a reference I can quote for such a bound? Any insights are much appreciated.
