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.