The Chromatic and Cochromatic Number of a Graph

Clearly, there are many ways that one can partition the vertex sets of graphs. In the first chapter of this work I examine the problem of determining, for a given graph, the minimum order of a vertex partition having specified properties. In the remaining chapters I concentrate on partitions of two types--those in which each subset induces an empty graph and those in which each subset induces an empty or a complete graph.\nThe chromatic number of a graph G is the minimum number of subsets into which V(G) can be partitioned so that each subset induces an empty graph. The cochromatic number of G is the minimum number of subsets into which V(G) can be partitioned so that each subset induces a complete or an empty graph. In the second chapter I discuss the relationship between chromatic and cochromatic numbers of graphs. I also extend known results in the field of cochromatic numbers.\nIn the third chapter I explore concepts in cochromatic theory which are analogous to well known topics in chromatic theory.\nThe acochromatic number of a graph G is the maximum order of all vertex partitions of G where each subset induces a complete or an empty graph but the union of any two does neither. I show in Chapter IV that the acochromatic number of a bipartite graph is bounded below by its edge independent number and above by this number plus one.\nIn the last chapter I discuss switching sets and sequences. I apply knowledge of chromatic and cochromatic theory to this concept.