1. Prove that when , the list-chromatic number of exceeds k.
2. Let f be a proper k-coloring of a k-chromatic graph G. Let T be a tree with vertex set . Prove that there is an edge-preserving map : V(T) V(G) such that = i for all i.
3. Prove that has an interval coloring using m + n - gcd(m,n) colors, and that fewer colors cannot suffice.
4. Prove that = 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.