List coloring

The list of coloring is a term in graph theory and a generalization of the edge color and the coloring node.

Definition

Is a graph and a family of sets of an arbitrary number, it means a valid node coloring for all vertices of the graph coloring from the lists or list coloring. A graph is called k -choosable if it is always a vertex coloring from these lists exist for all lists with k elements. K is the smallest, so that the graph is k -choosable, is the choice number and the graph is labeled.

Clearly that is a list of available colors to each node set, and the graph must be then colored so that two adjacent nodes never have the same color.

Similarly, you can define colorings of edges lists. The smallest k such that G for all lists, each with k colors is edge- is called listenchromatischer index and denoted by. Formally, the edge graph of is.

Example

For the above pictured graph with 5 nodes following is prescribed for a node coloring to each node a list of available colors. A valid node coloring from the lists would be eg

Properties

• Since list colorings are a generalization of ordinary colorings, and always applies. The chromatic number of the graph, and the number Kantenchromatische.
• If all lists are equal, the list coloring corresponds exactly to the edge coloring and node coloring.
• Every planar graph is 5 -choosable.
• For every bipartite graph with the maximum degree of the graph.
• Probably for every graph ( list coloring conjecture ). However, this has so far not been proven.