Lesson 4

Below we strengthen the just-proven theorem in two ways: first, we will show that it is possible to color with five colors, and second, not just color, but list-color. In the list coloring problem, for each vertex \(v \in V\) of the graph \(G(V,E)\) there is a given list of colors \(L(v)\), and the task is to color each vertex with one of the colors from its list so that any two adjacent vertices receive different colors. A graph is called list \(k\)-colorable if it can be properly colored for any vertex lists of size exactly \(k\). The list chromatic number \(\chi_{l}(G)\) of a graph \(G\) is the minimal such \(k\). It is easy to see that ordinary coloring is a special case of list coloring where all the lists are the same, therefore \[\chi(G) \le \chi_{l}(G) \ .\]

Problem. Is the graph shown below list-colorable?