Timeline for Edges of $K_n$ are colored, connected few-colored subgraph is needed
Current License: CC BY-SA 3.0
2 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Mar 6, 2015 at 13:03 | comment | added | Fedor Petrov | I am afraid that greedy algorithm as is does not provide any better bound, since it may easily happen that each color has about $n(1-\delta)$ components for $\delta=O(1/\sqrt{k})$: partition all vertices onto blocks of $\delta n$ vertices and for any pair of blocs A, B color all edges between A,B in a special color. | |
| Mar 5, 2015 at 18:09 | history | answered | Victor Kleptsyn | CC BY-SA 3.0 |