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.

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

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).