On \(r\)-Type-Constructions and \(\Delta\)-Colour-Critical Graphs

In this paper, we first generalize a classical result of B. Toft (\(1974\)) on \(r\)-type-constructions for graphs (rather than hypergraphs). We then demonstrate how this result can be utilized to construct colour-critical graphs, with a special focus on
\(\Delta\)-colour-critical graphs. This generalization encompasses most known constructions that generate small critical graphs. We also obtain upper bounds for the minimum excess function \(\eta(k,p)\) when \(4 \leq k \leq 6\); where
\[
\eta(k,p) = \min\limits_{G\in K(k,p)} \epsilon(G),
\]
in which \(\epsilon(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 \(\Delta = k\). Using these techniques, we construct an infinite family of \(\Delta\)-colour-critical graphs for \(\Delta = 5\) with a relatively small minimum excess function; Furthermore, we prove that \(\eta(6, 6n) \leq 6(n-1)\) (\(n\geq2\)) which shows that there exists an infinite family of \(\Delta\)-colour-critical graphs for \(\Delta = 6\).