Other Results
If BVC is true for two graphs, then BVC is true for their cartesian product.
To understand this theorem, we first have to know what a cartesian product is. You can find it here.
Zmazek and Zerovnik showed in their article Behzad-Vizing conjecture is true for cartesian product graphs
that when BVC is true for simple graphs G and H, then the conjecture is true for the also simple cartesian product G☐H.
The most important lemma in the proof of this theorem is:
If G and H are graphs with Δ(G)≤Δ(H), then χ"(G☐H)≤Δ(G)+χ"(H).
Now Δ(G☐H)=Δ(G)+Δ(H) (proof it for yourself if you don't want to assume this).
So if BVC is true for G and H, a corollary of the lemma is:
χ"(G☐H)≤Δ(G)+χ"(H)≤Δ(G)+Δ(H)+2=Δ(G☐H)+2.
Because G☐H is simple, this means that BVC holds for G☐H. The proof of the lemma is more technical and shows a
total colouring of G☐H with Δ(G)+χ"(H) colours.
Some bounds.
Although the boundary χ"(G)≤Δ(G)+2 is still unproven in BVC, there are some other upper bounds of χ"(G) known.
The upper bound χ"(G)≤χ'(G)+2⌈√ χ(G) ⌉ found by H.R. Hind in 1990
is quite famous and 6 years later improved by A.G. Chetwynd and R. Häggkvist. Later on, M. Molloy and B. Reed proved that χ"(G)≤ Δ(G)+1026 if Δ(G) is at least as large as a particular (not defined) constant.