Weakly completable critical sets for proper vertex and edge colourings of graphs (Q2760455)

A long-standing problem has been that of finding weakly completable critical sets for Latin squares and, in particular, determining the smallest Latin squares which have such sets. In this paper the analogous problem for graph colouring and determining the graphs of smallest size which possess weakly completable partial vertex or edge colourings are considered. It is shown that for every \(r\geq 3\) if \(G\) is a simple graph possessing a weakly completable subset of its vertex set \(V\) relative to an \(r\)-colouring of \(V\), then \(G\) has at least \(r+3\) vertices and \(4(r-1)\) edges. Furthermore, for every \(r\geq 3\), there is at least one connected graph reaching these bounds. A similar result holds for graphs having a weakly completable subset of its edge set \(E\) relative to an \(r\)-colouring, whenever \(|E|\geq 2r\).