Behzad-Vizing Conjecture

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 GH. The most important lemma in the proof of this theorem is:
If G and H are graphs with Δ(G)≤Δ(H), then χ"(GH)≤Δ(G)+χ"(H).
Now Δ(GH)=Δ(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:
Because GH is simple, this means that BVC holds for GH. The proof of the lemma is more technical and shows a total colouring of GH 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.