2020/03/21 by Murthy, T Srinivasa
#05C15 (primary) #11T06 #11T55 (secondary) #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics
paper · doi:10.48550/arxiv.2003.09658
Total Coloring of a graph is a major coloring problem in combinatorial mathematics, introduced in the early 1960s. A total coloring of a graph G is a map f:V(G) ∪ E(G) → K, where K 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 the same vertex v. The total chromatic number, χ''(G), is the minimum number of colors required for a total coloring of G. Behzad (1965), and Vizing (1968), conjectured that for any graph G χ''(G)≤ Δ+ 2. This conjecture is one of the classic unsolved mathematical problems. In this paper, we settle this classical conjecture by proving that the total chromatic number χ''(G) of a graph is indeed bounded above by Δ+2. Our novel approach involves algebraic settings over a finite field ℤp and Vizing's theorem is an essential part of the algebraic settings.