
4 Coloring Problems
1. Prove that when $\displaystyle m\geq k^{k}$, the listchromatic number of $\displaystyle K_{m,k}$ exceeds k.
2. Let f be a proper kcoloring of a kchromatic graph G. Let T be a tree with vertex set $\displaystyle \{w_1, w_2,..., w_k\}$. Prove that there is an edgepreserving map $\displaystyle \phi$ : V(T) $\displaystyle \rightarrow$ V(G) such that $\displaystyle f(\phi(w_i))$ = i for all i.
3. Prove that $\displaystyle K_{m,n}$ has an interval coloring using m + n  gcd(m,n) colors, and that fewer colors cannot suffice.
4. Prove that $\displaystyle \chi_L (K_{2,...,2,3})$= r, where there are r1 2's in the subscript of K.
I have worked other problems, but I am completely stuck on these 4. Thanks.