Proofs
How to proof the Behzad-Vizing conjecture? There is still no proof known, but there are a lot of proofs of different
cases.For example, BVC is true for graphs G with:
G is complete or G is complete bipartite.
We will proof this for Kn and n odd. For n even and the complete bipartite-case
you can read the article of Behzad, G. Chartrand and J.K. Cooper.
Assume n is odd. Because Δ(G)=n-1 we know χ"(G)≥n. Define for p=1,2,..,n the
set of edges
S(p)={{p-q (mod n), p+q (mod n)}|q=1,2,..,(n-1)/2}.
It can be observed that the elements of S'(p)=S(p)⋃{p} can receive the same coulour in a total colouring of G.
Now every vertex or edge is in exactly one S'(p) and therefore there is a total colouring with n colours. This means χ"(G)=n=Δ(G)+1.
Δ(G)=3
The proof of this theorem was given by N. Vijayaditya and M.Rosenfeld idenpendently. Rosenfeld's proof proceeds by induction on the number of vertices in a graph G with Δ(G)=3. An interesting observation in the proof is that Roosenfeld assumes that G is 3-regular. If there is a vertex v in G of degree 2, we can smooth v by deleting it and adding a new edge between the old neighbours u and w of v. If there is a total colouring with 5 colours for the new graph G', then there is one for G, because u and w have degree less than or equal to 3 and so there are free colours to choose'. That's why Rosenfeld assumes that G is 3-regular.
Δ(G)=4 or 5
The man responsible for these results is A.V. Kostochka. In 1977, he proved BVC' (and thus BVC) for Δ(G)=4. A few years later, also his proof for Δ=5 was published. Unfortunately, it was written in Russian. But in this article, we can view an English proof for the Δ=5-case.
Δ(G)≥n-5, where n is the number of vertices in G.
H.P. Yap and K.H. Chew proved BVC for simple graphs G with Δ(G)=n-5. At that moment, the other case were already proven by again Yap and some other mathematicans in an article from 1989. The proof sequentially treats the cases Δ(G)=n-4, Δ(G)=n-3. Because G is a subgraph of Kn, it's chromatic number is less than or equal to the chromatic number n of Kn. This argument can prove the cases Δ(G)=n-2 and Δ(G)=n-1.
δ(G)≥5⁄6(n+1).
Here δ(G) denotes the minimum degree of a vertex in G and n is again the number of vertices in G. The proof of this theorem can be found here.
G planar and Δ(G)≠6.
A planar graph is a graph that can be drawn on the plane without intersecting edges. For more info about planar graphs, see this bachelor thesis (in Dutch). We know already that BVC is true for graphs (and thus for planar graphs) with Δ(G)≤5. In different articles it is proved that if a planar graph G has Δ(G)≥11, Δ(G)=10 or Δ(G)=9, χ"(G)=Δ(G)+1 must hold. In the last mentioned article it is said that BVC is also true if Δ(G)=8, more information can be found in the book Graph Coloring Problems of R. Jensen and B. Toft. Finally, D. Sanders and Y.Zhao proved the Δ(G)=7 -case.