Group:Student Seminar
Title: Rainbow Coloring
Speaker: Hongyu Liang University
Time: 2010-10-21 16:00-2010-10-22 17:00
Venue: FIT 1-222


In this talk I'll speak of two interesting problems related to the graph concept called rainbow connectivity. Let rc(G) (the rainbow connectivity of G) denote the minimum number of colors that can make G rainbow-connected (i.e., every two vertices are connected by a path on which all edges have distinct colors). The first result says that rc(G)=O(n/delta(G)), that is, rc(G) is reciprocal to its minimum degree. The second one is that, given a graph G with rc(G)=2, can we rainbow-color it with o(n) colors in polynomial time? I'll talk about our partial results in attacking it.

Short Bio: