Behzad-Vizing Conjecture


For a full understanding of the Behzad-Vizing conjecture, we will explain some definitions at this page. After that, we are going to talk about some variants of the conjecture.

There are different types of graph colourings. For example, for a graph G is:

In a simple graph loops and multiple edges are disallowed. In a multigraph they are not. The degree of a vertex v is the number of edges that have v as an endpoint. A loop increases the degree with two.

Sometimes the requirement of a graph being simple isn't added at Behzad-Vizing conjecture. A well-known site as open problem garden makes this mistake. To realise that this is a mistake, look at this graph G with Δ(G)=χ"(G)=4.

There are not only different names of the Behzad-Vizing conjecture abroad, the definitions of it are also not always the same. For example, there is a slight variant that has some space for multigraphs:

Behzad-Vizing Conjecture'

If we denote the maximum degree of a vertex in a multigraph G by Δ(G) and the total chromatic number of G by χ"(G), then:
Note that the original conjecture (BVC) follows as a consequence of this variant (BVC'), since a simple graph has obviously the property that χ"(G)≥Δ(G)+1.

Hereafter, if we say "BVC is true for a graph G", we mean χ"(G)=Δ(G)+1 or χ"(G)=Δ(G)+2. With "BVC' is true for a graph H" we mean χ"(H)≤Δ(H)+2.