I am trying to understand the definition of list colouring. I have looked in a book by Matousek & Nesetril, one by D.B.West, and the wikipedia page. But I don't quite get it.
"A graph is list k-colourable if every assignment of k-element lists to the vertices permits a proper list colouring." What exactly does this mean? Wikipedia gives the example of $K_{2,4}$. Let the components be $A,B,X,Y,Z,W$ and let $A,B$ be {red, blue} and {green, black}, and the others {red, green}, {red, black}, {blue, green}, and {blue, black}.
We cannot 2-colour it this way, and so our graph is not 2-choosable. My questions are
How do we decide how many colours to choose from when making the list?
Could you give an example, different to the one above to help my understanding of the concept?
A list coloring of a graph is the same thing as a usual vertex coloring, except that instead of having a global set of colors to choose from for each vertex, there is a different list for each vertex.
For instance, with $K_5$, the complete graph on 5 vertices, you can give a proper vertex coloring with colors from {red, blue, black, green, yellow}.
A list coloring would be a proper coloring with constraints such as: $v_1$ has to be red or blue, $v_2$ has to be blue or black, $v_3$ has to be red or green, $v_4$ has to be green or yellow, and $v_5$ has to be red or black.
In that case, it is possible to find a proper coloring (red, blue, green, yellow, black). But with a different set of pairs of colors to choose from at each vertex, it wouldn't be:
For instance, every vertex has to be red or blue. Obviously no proper coloring can be chosen from those lists.
So, $K_5$ is not list 2-colorable. It's also not list 4-colorable, because I can find a way to give four possible colors for each vertex, such that no proper coloring can be found (just use the same four colors at each).
In fact the list chromatic number of $K_5$ is 5: as long as every vertex has 5 colors to choose from, you can always find a proper coloring, no matter what those lists look like.