4
$\begingroup$

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?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

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$,

which is a contradiction.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Thank you for this! It will take me a little while to absorb it, but for now I’ll just say that I do care about it being a tree and not a forest. However, it would still be interesting to me to know when there is a forest with an a priori bound on the total number of components (I’d like the number of components to be bounded in terms of, let’s say, square root of the number of colors). $\endgroup$
    – TA31455
    Commented May 2, 2020 at 21:29
  • $\begingroup$ 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. $\endgroup$
    – Tony Huynh
    Commented May 3, 2020 at 7:11
  • $\begingroup$ Hi Tony, thanks again! And yes, I understand that in general one can’t hope for a bound on the number of components in terms of the number of colors. What I meant was that while what I’d really like is connectedness (i.e., one component), I would be content with a situation where such a bound on the number of components held. While you’re right that this won’t happen in general, I’m asking for some sufficient conditions on the graph and the coloring that would lead to such a bound $\endgroup$
    – TA31455
    Commented May 3, 2020 at 15:25
  • $\begingroup$ For example, I could imagine something like the following being true: Given N, C> 0, there exists K so that if the min (or perhaps average) chromatic degree of an edge colored graph with at most N vertices and C colors is at least K, there exists a connected total rainbow subgraph. $\endgroup$
    – TA31455
    Commented May 3, 2020 at 21:46

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .