In graph theory

Graph theory

In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and a collection of edges that connect pairs of...

, total coloring is a type of coloring on the vertices and edges of a graph.
When used without any qualification, a total coloring is always assumed to be proper in the sense that no adjacent vertices, no adjacent edges, and no edge and its endvertices are assigned the same color.
The total chromatic number χ″(G) a graph G is the least number of colors needed in any total coloring of G.

The total graph T = T(G) of a graph G is a graph such that (i) the vertex set of T corresponds to the vertices and edges of G and (ii) two vertices are adjacent in T if and only if their corresponding elements are either adjacent or incident in G.
Then total coloring becomes a (proper) vertex coloring

Graph coloring

In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called "colors" to elements of a graph subject to certain constraints. In its simplest form, it is a way of coloring the vertices of a graph such that no two adjacent vertices share the...

 of the total graph.

Some properties of χ″(G):

1. χ″(G) ≥ Δ(G) + 1.
2. χ″(G) ≤ Δ(G) + 10²⁶.