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. ${\displaystyle G=(V,E)}$ ${\displaystyle (F_{v})_{v\in V}}$ ${\displaystyle c:v\mapsto F_{v}}$ ${\displaystyle F_{v}}$ ${\displaystyle ch(G)}$

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 . ${\displaystyle ch'(G)}$ ${\displaystyle ch'(G)=ch(L(G))}$ ${\displaystyle L(G)}$ ${\displaystyle G}$

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. ${\displaystyle i}$ ${\displaystyle F_{i}}$ ${\displaystyle c(3)=c(5)=b\;,\;c(1)=c(4)=a\;,c(2)=e}$

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 . ${\displaystyle ch(G)\geq \chi (G)}$ ${\displaystyle ch'(G)\geq \chi '(G)}$ ${\displaystyle \chi (G)}$ ${\displaystyle \chi '(G)}$
• If all lists are the same, the list coloring corresponds exactly to the edge coloring or node coloring . ${\displaystyle F_{v}}$
• Every planar graph can be colored in 5 lists.
• For every bipartite graph , where is the maximum degree of the graph. ${\displaystyle ch'(G)=\chi '(G)=\Delta (G)}$ ${\displaystyle \Delta (G)}$
• Presumably applies to every graph ( list coloring assumption ). However, this has not yet been proven. ${\displaystyle ch'(G)=\chi '(G)}$

literature

• Reinhard Diestel : graph theory . 4th edition. Springer, Berlin 2010, ISBN 978-3-642-14911-5 (354 pages, online version ).