Semi-total graph colourings, the beta parameter, and total chromatic number

A semi-total colouring  , μμ, of a graph G   with maximum degree ΔΔ uses Δ+1Δ+1 colours and has the properties of a total colouring except that adjacent vertices need not have distinct colours. A beta edge   is an edge v1v2v1v2 such that μ(v1)=μ(v2)μ(v1)=μ(v2). The beta parameter of G  , β(G)β(G), is the minimum number of beta edges in any semi-total colouring of G.A critical edge of G is an edge whose deletion reduces the total chromatic number of G   to Δ+1Δ+1. We derive the beta parameters of cycle and complete graphs; a quadratic bound for ββ in terms of ΔΔ for any graph with a critical edge; and a log-linear bound for any graph with a critical edge that is not contained in any triangle.