[Solved] CSDS455 Homework 14-k-chromatic graph

Hadwigers Conjecture (1943 still open): Every k-chromatic graph contains a K_k-minor (we can form a K_k through edge contractions or deletions of G).

Hajoss Conjecture (1961 proved false in 1979): Every k-chromatic graph contains a subdivision of a K_k (we take a K_k and add extra vertices along the edges).

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.