Total coloring

The total coloring is a term used in graph theory and a generalization of both the edge coloring and from the node coloring .

definition

Let be a graph and a mapping, which assigns a natural number (in this context also called color) to every edge and every node. is called a valid total coloring or valid k-total coloring if for all adjacent or incident elements off applies. In particular, the graph is colored both at the edges and at the nodes, whereby it is again required that neighboring elements are given different colors. In addition, there is the promotion that an edge is colored differently than its endpoints. ${\displaystyle G=(V,E)}$ ${\displaystyle c\colon {V}\cup {E}\rightarrow \{1,\dotsc ,k\}}$ ${\displaystyle c}$ ${\displaystyle c(i)\neq c(j)}$ ${\displaystyle {V}\cup {E}}$

If a graph has a valid -Total coloring, but no valid -Total coloring, then the total chromatic number is called by and is denoted by. ${\displaystyle k}$ ${\displaystyle (k-1)}$ ${\displaystyle k}$ ${\displaystyle G}$ ${\displaystyle \chi _{T}}$

example

A total coloring of the (of the complete graph with 4 nodes) ${\displaystyle K_{4}}$

The graph shown on the right is provided with a valid total coloring, since every colored edge or node is never adjacent to an edge or node of the same color. The coloring uses five different colors, but in order to determine the total chromatic number, it would first have to be shown that there is no valid total coloring that gets by with fewer colors.

properties

• Obviously , for any graph , where is the maximum degree, is the chromatic index and the chromatic number . ${\displaystyle \Delta (G)+1\leq \chi _{T}(G)\leq \chi '(G)+\chi (G)}$ ${\displaystyle \Delta (G)}$ ${\displaystyle \chi '(G)}$ ${\displaystyle \chi (G)}$
• It is true that it is necessarily bipartite . ${\displaystyle \chi _{T}(G)=\chi '(G)+\chi (G)}$ ${\displaystyle G}$
• It is assumed that applies to simple graphs ( assumption of total coloring ). So far, however, this could only be shown for restricted graph classes, for example for bipartite graphs. ${\displaystyle \chi _{T}(G)\leq \Delta (G)+2}$

literature

• Lutz Volkmann: Fundamente der Graphentheorie , Springer (Vienna) 1996, ISBN 3-211-82774-9 ( newer, online version "Graphs on all corners and edges" ; PDF; 3.7 MB)