Problem 1: Prove the following graph has chromatic number 7 but does not contain a subdivision of a
7-clique.
Problem 2: Prove that the following graph has chromatic number 8 but does not contain a subdivision of an 8-clique.
Problem 3: In list coloring, each vertex is given a list of colors and must choose one color of the list. As before, we require each vertex to be assigned a different color. A graph is k-list colorable (or k-chooseable) if for any way we can assign a list of k colors to each vertex, there exists a legal coloring. ch(G) is the smallest value k such that G is k-list colorable.
Give an example of a graph that is 2-colorable but not 2-list colorable.
Problem 4: Prove that if G is k-list colorable then G is k-colorable.
