Disconnected-Colorings of Graphs

摘要

A disconnected-coloring (or D-coloring) of a graph G = (V,E) is a partition pi = V1,V2,...,Vn of V such that for every i, the subgraph induced by the subset Vi is disconnected. The D-chromatic number Chi sub d (G) of G is the smallest number of color classes (subsets) in any D-coloring of G. This paper contains a large variety of results for D-colorings and Chi sub d which are very similar to corresponding results that have been established for the traditional colorings and chromatic number Chi(g) of graphs; in particular, analogs are given for established results on (1) bounds for the chromatic and achromatic number, (2) colorings of planar graphs, (3) critical graphs, (4) the line-chromatic number, and (v) uniquely-colorable graphs. These new results indicate that the established results reveal much less about properties of colorings than they do about concepts which are much more general. They also reveal that most of the established results on coloring are really very simple. One conclusion that can be drawn from this is that one has not learned very much yet about the concept of coloring a graph. Another conclusion is that there is now emerging a new theory of partitions of graphs of which the theory of colorings is but a part. (Author)