## 4 Coloring Problems

1. Prove that when $m\geq k^{k}$, the list-chromatic number of $K_{m,k}$ exceeds k.

2. Let f be a proper k-coloring of a k-chromatic graph G. Let T be a tree with vertex set $\{w_1, w_2,..., w_k\}$. Prove that there is an edge-preserving map $\phi$ : V(T) $\rightarrow$ V(G) such that $f(\phi(w_i))$ = i for all i.

3. Prove that $K_{m,n}$ has an interval coloring using m + n - gcd(m,n) colors, and that fewer colors cannot suffice.

4. Prove that $\chi_L (K_{2,...,2,3})$= r, where there are r-1 2's in the subscript of K.

I have worked other problems, but I am completely stuck on these 4. Thanks.