The Chromatic and Cochromatic Number of a Graph
John Gimbel · ScholarWorks - WMU (Western Michigan University) · 1984
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. The 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. In the third chapter I explore concepts in cochromatic theory which are analogous to well known topics in chromatic theory. The 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. In the last chapter I discuss switching sets and sequences. I apply knowledge of chromatic and cochromatic theory to this concept.