Fractional total colouring (Q807633)

The total colouring problem of a graph G is to colour all vertices and edges of G with minimum number of colours in such a way that no two adjacent or incident vertices or edges receive the same colour. \textit{Behzad} conjectures in 1965 that a simple graph G can always be totally coloured using two more colours than the maximum degree \(\Delta\) (G) of vertices in G. If the conjecture is true, then the total colouring number of a graph is always equal to either \(\Delta (G)+1\), or \(\Delta (G)+2\). There is an equivalent integer programming formulation. The author proves that the linear programming relaxation of this integer programming has its fractional value bounded between \(\Delta (G)+1\) and \(\Delta (G)+2\). This result gives a proof of a weakening of the mentioned Behzad's conjecture.