CSDS 455: Applied Graph Theory
Homework 14
Hadwiger’s Conjecture (1943 - still open): Every k-chromatic graph contains a Kk-minor (we can form a Kk
through edge contractions or deletions of G).
Haj´os’s Conjecture (1961 - proved false in 1979): Every k-chromatic graph contains a subdivision of a Kk
(we take a Kk 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.
