List coloring
List coloring is a term in graph theory and a generalization of edge coloring and node coloring .
definition
If a graph and a set family are arbitrary sets, then a valid node coloring for all nodes of the graph is called a coloring from the lists or list coloring . A graph is called k-list colorable if there is always a node coloration from these lists for all lists with k elements. The smallest k, so that the graph can be colored k-lists, is called the list chromatic number of the graph and is denoted by.
A list of available colors is clearly given for each node and the graph must then be colored in such a way that two neighboring nodes never have the same color.
In the same way, edge coloring can be defined from lists. The smallest k, so that G can be edge-colored for all lists with k colors each, is called the list-chromatic index and denoted by. Is formal , where is the edge graph of .
example
For the graph with 5 nodes shown above, a list of available colors for node coloring is given for each node . A valid node coloring from the lists would be e.g. B.
properties
- Since list coloring are a generalization of ordinary stains, we always have and . Here is the chromatic number of the graph and the edge chromatic number .
- If all lists are the same, the list coloring corresponds exactly to the edge coloring or node coloring .
- Every planar graph can be colored in 5 lists.
- For every bipartite graph , where is the maximum degree of the graph.
- Presumably applies to every graph ( list coloring assumption ). However, this has not yet been proven.
literature
- Reinhard Diestel : graph theory . 4th edition. Springer, Berlin 2010, ISBN 978-3-642-14911-5 (354 pages, online version ).