Timeline for “Total rainbow” trees
Current License: CC BY-SA 4.0
9 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| May 3, 2020 at 21:46 | comment | added | TA31455 | 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. | |
| May 3, 2020 at 15:25 | comment | added | TA31455 | 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 | |
| May 3, 2020 at 7:11 | comment | added | Tony Huynh | 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. | |
| May 2, 2020 at 21:29 | comment | added | TA31455 | 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). | |
| May 2, 2020 at 21:17 | history | edited | Tony Huynh | CC BY-SA 4.0 |
added 35 characters in body
|
| May 2, 2020 at 21:10 | history | edited | Tony Huynh | CC BY-SA 4.0 |
added 35 characters in body
|
| May 2, 2020 at 20:57 | history | edited | Tony Huynh | CC BY-SA 4.0 |
added 199 characters in body
|
| May 2, 2020 at 20:46 | history | edited | Tony Huynh | CC BY-SA 4.0 |
added 199 characters in body
|
| May 2, 2020 at 20:37 | history | answered | Tony Huynh | CC BY-SA 4.0 |