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!

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?

Let $G= (V,E)$ be a simple finite graph which is (not necessarily properly) edge-colored. A $\textit{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 $\textit{total rainbow tree}$ to be a (not necessarily spanning!) tree in G so that each color appears $\textit{exactly}$ once.

While it’s easy to find results in the literature about rainbow spanning trees (where sometimes the term $\textit{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:

$\textbf{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!

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!