The Yale Combinatorics and Probability Seminar
April 20, 2012
2:00 p.m., LOM 206

Sign up to meet with speaker

Speaker: Alan Frieze, CMU
Title: Some coloring problems on random graphs

Abstract: We will discuss some problems related to coloring the edges or vertices of a random graph. In particular we will discuss results on (i) the game chromatic number; (ii) existence of rainbow Hamilton cycles; (iii) rainbow connectivity. For the game chromatic number we consider the two player game where each player takes turns in coloring the vertices of a graph G from one of k colors. Both players must color a vertex with a color distinct from its neighbors. Player A tries to ensure that all vertices of G are colored and player B tries to ensure that at some point, there is a vertex that cannot be colored. The game chromatic number is the minimum number of colors needed so that A can be guaranteed to win. We show that the game chromatic number of a random graph is within a constant factor of the chromatic number, but this factor is greater than one. Joint work with Tom Bohman, Simi Haber, Mikhail Lavrov, Benny Sudakov.

We next consider coloring the edges of a graph. A set of edges S is rainbow colored if each edge of S is differently colored.

An edge-colored graph is rainbow connected if there is a rainbow path between each pair of vertices. The rainbow connectivity of a connected graph is the minimum number of colors needed to make it rainbow connected. We prove that at the connectivity threshold, the rainbow connectivity of G(n,p) is asymptotically equal to the maximum of the number of vertices of degree one and the diameter.

Joint work with Charalampos Tsourakakis.

We finally discuss the threshold for a randomly edge-colored random graph to have a rainbow Hamilton cycle. We prove that with (1+o(1)) n colors, we only need 1+o(1) times the number needed to ensure that G(n,p) is Hamiltonian.

Joint work with Po Shen-Loh