University of Surrey

Test tubes in the lab Research in the ATI Dance Research

Uniquely completable and critical sets for graph colourings and Latin squares.

Burgess, D.R.B. (1998) Uniquely completable and critical sets for graph colourings and Latin squares. Doctoral thesis, University of Surrey (United Kingdom)..

Available under License Creative Commons Attribution Non-commercial Share Alike.

Download (24MB) | Preview


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.

Item Type: Thesis (Doctoral)
Divisions : Theses
Authors :
Burgess, D.R.B.
Date : 1998
Contributors :
Depositing User : EPrints Services
Date Deposited : 09 Nov 2017 12:11
Last Modified : 16 Mar 2018 16:57

Actions (login required)

View Item View Item


Downloads per month over past year

Information about this web site

© The University of Surrey, Guildford, Surrey, GU2 7XH, United Kingdom.
+44 (0)1483 300800