Abstract
It is possible for certain combinatorial structures to be uniquely defined with only partial information. The amount of information may be reduced until each part is critical for reconstruction. This thesis examines such 'uniquely completable' and 'critical sets' for 'Latin squares' and 'graph colourings', focusing on small and minimal critical sets. We aim to contribute to the current knowledge but also to illustrate why this knowledge is limited. We present critical sets of small cardinal in one of a certain family of Latin squares and prove that for a vast range of Latin squares there is at least one uniquely completable set which cannot directly be shown to be such. This existence of these 'weakly completable sets' is also dealt with for vertex- and edge-colourings of graphs and our result for edge-colourings of bipartite graphs is related to that for Latin squares. For some well-known families of graphs we show how the cardinality of corresponding minimal critical subsets of vertices (and, in some cases, edges) of a graph varies with the choice of colouring. Our results are given more significance by the fact that there are relatively few known critical sets of low cardinal in Latin squares and even fewer for colourings of graphs. This is partly explained by our demonstration of the widespread existence of weakly completable sets about which even less had hitherto been known.