Total coloring

The total coloring is a term from graph theory and a generalization of both the edge-coloring as well as the node coloring.

Definition

Be a graph and a mapping which assigns each edge and each node a natural number (in this context also called color). is called a valid coloring total k -total coloring or valid if for all adjacent or incident elements applies. In particular, the graph is thus both edge- and node- colored, being demanded again that adjacent elements receive different colors. Then there is the promotion that an edge is colored differently than their endpoints.

Has a valid graph Total color, but no valid Total color, it means the number of total chromatic and is denoted by

Example

The graph shown on the right is accompanied by a valid total coloring, as each colored edge or node is never adjacent to an edge or a node of the same color. Although the coloring used five different colors, but to determine the total chromatic number, would first be shown that there is no valid total coloring, which makes do with fewer colors.

Properties

• For each graph is obviously true, the maximum degree, the chromatic index and the chromatic number.
• Applies, as is necessarily bipartite.
• It is believed that for a simple graph applies (total coloring guess). However, this has so far been shown only for restricted graph classes, such as for bipartite graphs.