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.
Reviews
There are no reviews yet.