A proof of the Total Coloring Conjecture
A total coloring of a graph G is a map f:V(G) βͺ E(G) βπ¦, where π¦ is a set of colors, satisfying the following three conditions: 1. f(u) β f(v) for any two adjacent vertices u, v β V(G); 2. f(e) β f(e') for any two adjacent edges e, e' β E(G); and 3. f(v) β f(e) for any vertex v β V(G) and any edge e β E(G) that is incident to same vertex v. The total chromatic number, Οβ(G), is the minimum number of colors required for a total coloring of G. Behzad and Vizing independently conjectured that, for any graph G, Οβ(G)β€Ξ + 2. This is one of the classic mathematical unsolved problems. In this paper, we settle this classical conjecture by proving that the totalchromatic numberΟβ(G) of a graph is indeed bounded above by Ξ+2. Our novel approach involves algebraic settings over finite field β€_p and application of combinatorial nullstellensatz.
READ FULL TEXT