# “Total rainbow” trees

Let $$G= (V,E)$$ be a simple finite graph which is (not necessarily properly) edge-colored. A rainbow spanning tree refers to a spanning tree T of G such that no color appears more than once amongst the edges of T.

Alternatively, define a total rainbow tree to be a (not necessarily spanning!) tree in G so that each color appears exactly once.

While it’s easy to find results in the literature about rainbow spanning trees (where sometimes the term heterochromatic is used instead of rainbow), e.g. necessary and sufficient conditions for existence & efficient algorithms for finding them, I haven’t been able to find any information relating to the latter concept. In particular, I made up the terminology so it’s possible it’s been studied under a different name.

This motivates the following question:

Question: Are there any known necessary and/or sufficient conditions on G and the associated coloring for the existence of a total rainbow tree?

Of course there are trivial cases, like when one uses only one color (then any edge is a total rainbow tree). I’m interested in a family of graphs arising in surface topology for which the number of colors is large, but still much smaller than the number of vertices (I am happy to say more about the problem for anyone who is interested). The problem is solvable if there exists a rainbow spanning tree, but this is impossible when the number of colors is much smaller than the number of vertices. But I realized I can solve the problem in another way if there exists a total rainbow tree which is what led to the above question.

I would also be happy to know something about when there exists a heterochromatic tree so that some definite fraction of the full set of possible colors appear. Thanks for reading!

Edit: it turns out I can simplify the potential solution to the problem of interest, and now I only need the existence of a connected total rainbow subgraph (so, we drop the assumption of being a tree). Thus the new and improved question is:

What are necessary and sufficient conditions on a (not necessarily properly) edge-colored graph G for the existence of a connected total rainbow subgraph?

If you do not care about connectedness, then a necessary and sufficient condition is given by the matroid intersection theorem. Let $$G=(V,E)$$ be a (not necessarily properly) edge-colored graph. Define a total forest to be the set of edges of a forest which contains every colour exactly once.

Let $$M_1$$ be the matroid with ground set $$E$$, where a set is independent if and only if it contains at most one edge of each colour. Let $$M_2$$ be the matroid with ground set $$E$$ where a set is independent if and only if it does not contain a cycle. Let $$r_1$$ and $$r_2$$ be the rank functions of $$M_1$$ and $$M_2$$, and let $$t$$ be the total number of colours. Observe that a total rainbow forest exists if and only if $$M_1$$ and $$M_2$$ have a common independent set of size $$t$$. By the matroid intersection theorem this is true if and only if for all $$A \subseteq E$$,

$$r_1(A) + r_2(E \setminus A) \geq t$$.

Moreover, it is clear that independence testing for $$M_1$$ and $$M_2$$ can both be done in polynomial-time. Therefore, by running the matroid intersection algorithm, we can find a total forest (if it exists) in polynomial-time, or a set $$A \subseteq E$$ such that

$$r_1(A) + r_2(E \setminus A) < t$$.

Note that such a set $$A$$ certifies that no total forest exists. To see this, observe that if $$T$$ is the set of edges of a total forest, then

$$t=|T|=|T \cap A| +|T \cap (E \setminus A)| \leq r_1(A)+r_2(E \setminus A) < t$$,

• In general, the total number of components can be much more than the square root of the number of colours.. To see this, colour the $n$-cycle with $t$ colours where each colour class is a path with $n/t$ edges. If $t \leq n/2$, then the largest connected rainbow subgraph has at most $2$ edges. Therefore, every total forest contains at least $t/2$ components. – Tony Huynh May 3 at 7:11