Let $G$ be a graph and let $A_1, A_2 \subseteq V(G)$ be disjoint sets of vertices. Let us call $(A_1, A_2)$ independent if there exist vertex-disjoint trees $T_1, T_2 \subseteq G$ within $G$ which cover the two sets in the sense that $A_1 \subseteq V(T_1)$, $A_2 \subseteq V(T_2)$.

(I) The problem I would like to pose is to characterise the independent pairs of sets of vertices. I am not aware of any existing literature on this problem and would be grateful for suitable pointers.

In the case where $|A_1| = |A_2| = 2$, a complete characterisation was given by Seymour ("Disjoint paths in graphs") and, independently, by Thomassen ("2-Linked Graphs"). Essentially, up to a reduction step, the pair $(\{x_1, y_1 \}, \{x_2, y_2\})$ is independent unless $G$ has a drawing in the plane with one face containing these four specified vertices in order $(x_1, x_2, y_1, y_2)$, which is an obvious obstruction to the existence of two disjoint trees covering the sets.

A complete characterisation of the general case might be out of reach, but I'm having a hard time even coming up with "new" obstructions which do not come from the consideration of just pairs of vertices.

What are some good examples where $(A_1, A_2)$ is not independent, although for any $B_1 \subseteq A_1, B_2 \subseteq A_2$ with $|B_1| = |B_2|$, the pair $(B_1, B_2)$ is independent?

(II) I am also interested in the following notion derived from the above. Call a set $A \subseteq V(G)$ agile if for every bipartition $A = A_1 \cup A_2$ of $A$, the pair $(A_1, A_2)$ is independent. It is easy to see that $V(G)$ is agile if and only if $G$ is a complete graph. As a somewhat different example, take a complete bipartite graph $K_{2,t}$. Then the set of all degree-2 vertices is agile.

The containment of a large agile set may be regarded as a measure of the complexity of a graph. If $H$ is a minor of $G$ and $H$ has an agile set $A$, then $G$ contains an agile set $A'$ with $|A'| \geq |A|$. Based on this, it is not hard to show that $G$ contains an agile set of order 4 if and only if $G$ is not outerplanar.

Is there, for every integer $t$, an integer $m(t)$ such that every graph which contains an agile set of size at least $m(t)$ contains $K_{2,t}$ as a minor?

I'd be happy about any sort of insights you can contribute to these questions as well as to pointers to relevant literature. Thank you very much in advance!


Here is a small example

where $(A_1, A_2)$ is not independent, although for any $B_1 \subseteq A_1, B_2 \subseteq A_2$ with $|B_1| = |B_2|$, the pair $(B_1, B_2)$ is independent?

a tetraed-like graph

$A_1$ consists of the two vertices labelled $1$.

$A_2$ consists of the three vertices labelled $2$.

$(A_1, A_2)$ is not independent because all the vertices labelled $3$ are required to connect $A_2$ and none would be left to connect $A_1$.

$(A_1, B_2)$ is independent for any $B_2 \subset A_2$ with $|B_2|=2$ because only two vertices labelled $3$ are required to connect any $B_2$, leaving the other free to connect $A_1$.

The graph is planar -- move one $1$ to the outer face.

I have no idea whether some simple kind of obstruction can be derived from such an example.

| cite | improve this answer | |
  • 1
    $\begingroup$ Thank you very much for your example! It seems that you might as well remove the leaves and relabel $3 \to 2$ for the other three. (General reduction rule: if there is a cutvertex $v$ for which distinct components of $G - v$ meet $A_i$, then we may as well add $v$ to $A_i$ without changing dependency. If $v$ already lies in $A_j$, $j \neq i$, then the pair is necessarily dependent.) The resulting triple $(G', A_1', A_2')$ is a 'trivially dependent' example, since one of the two sets separates the other (the vertices of $A_1$ lie in distinct components of $G - A_2$). $\endgroup$ – monkeymaths Aug 16 '18 at 13:51
  • $\begingroup$ Thank you for you kind words while I have been close to trivial! What about adding edges from all $1$'s to all $2$'s in my initial example? Then the $3$'s are not cutvertices anymore. Or is it an elementary reduction rule as well to remove any edge between $A_1$ and $A_2$? I'll look for yet another modification so as to exhaust all simple reduction rules. $\endgroup$ – Claude Chaunier Aug 16 '18 at 15:26
  • 1
    $\begingroup$ Well, yes, edges between $A_1$ and $A_2$ are of no use when trying to find those trees, so this seems like a straightforward reduction rule. But finding a 'right' set of reduction rules which really gets you anywhere is part of the (wide open, at least to me) problem. $\endgroup$ – monkeymaths Aug 16 '18 at 19:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.