In this paper we first generalize a classical result of B. Toft
(1974) on r-type-constructions for graphs (rather than
hypergraphs) and then we show how the result can be used to
construct colour-critical graphs with a special focus on
∆-colour-critical 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)=2|E(G)|−|V(G)|(k−1), and K(k,p) is the class of all
k-colour-critical graphs on p vertices with ∆ = k. We use
the techniques to construct an infinite family of
∆-colour-critical 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 ∆-colour-critical graphs for ∆ = 6.
Download TeX format
|
