In this paper we first generalize a classical result of B. Toft
(1974) on rtypeconstructions for graphs (rather than
hypergraphs) and then we show how the result can be used to
construct colourcritical graphs with a special focus on
∆colourcritical graphs. This generalization covers most
of known constructions which generate small critical graphs. We
also obtain some upper bounds for the minimum excess
function η(k,p) when 4 ≤ k ≤ 6; where
η(k,p)= 
min
G ∈ K(k,p)

ϵ(G), 

in which ϵ(G)=2E(G)−V(G)(k−1), and K(k,p) is the class of all
kcolourcritical graphs on p vertices with ∆ = k. We use
the techniques to construct an infinite family of
∆colourcritical graphs for ∆ = 5 with a relatively
small minimum excess function; and we prove that η(6,6n) ≤ 6(n−1)(n ≥ 2) which shows that there exists an infinite family
of ∆colourcritical graphs for ∆ = 6.
Download TeX format
