Abstract

List Coloring Bipartite Graphs

Bill Cuckler
Mon Jan. 26 at 1:10pm in Hill 423

I will sketch a proof of the following two related results:

1. Any bipartite graph with minimum degree d has list chromatic number at least order log d, due to Alon.

2. Any bipartite graph with maximum degree d has list chromatic number at most order d/ log d, a very special case of a theorem due to Johansson.

Both of the proofs are probabilistic. I will also mention some related results and related open problems.