On partitioning an arbitrarily given set of elements of a finite Boolean algebra into the minimum number of sets of compatible elements

Abstract

During the past several years at the United States Naval Postgraduate School there has been much interest in obtaining an efficient method for making a time schedule for classes. A mathematical model for a simplified version of this scheduling problem was devised by several faculty members, and this paper is a study of this model. This paper, while not offering a general solution to the simplified scheduling problem, does provide insight into the problem and suggests areas for future study that may lead to a general solution. The paper is presented in four parts, the first being an explanation of the problem in terms of Boolean algebra. The second part restates the problem in terms of graph theory, showing that this problem is the same as the problem of finding the chromatic number of a given graph. The third part is an attempt to gain insight into a solution of this problem by an exhaustive study of all graphs of order six and less, which are tabulated along with certain of their attributes. The fourth part is a study of certain random graphs of higher order. Among other things this study uses the digital computer to find the number of complete subgraphs of every order within each graph examined