On $r$-Type-Constructions and $\mathrm{\Delta }$-Colour-Critical Graphs

Abstract

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
$\mathrm{\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\le k\le 6$; where
$$\eta (k,p)=\underset{G\in K(k,p)}{min}ϵ(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 $\mathrm{\Delta }=k$. Using these techniques, we construct an infinite family of $\mathrm{\Delta }$-colour-critical graphs for $\mathrm{\Delta }=5$ with a relatively small minimum excess function; Furthermore, we prove that $\eta (6,6n)\le 6(n-1)$ ($n\ge 2$) which shows that there exists an infinite family of $\mathrm{\Delta }$-colour-critical graphs for $\mathrm{\Delta }=6$.