Subcolorings and the subchromatic number of a graph Original Research Article

We consider the subchromatic number χS(G) of graph G, which is the minimum order of all partitions of V(G) with the property that each class in the partition induces a disjoint union of cliques. Here we establish several bounds on subchromatic number. For example, we consider the maximum subchromatic number of all graphs of order n and in so doing answer a question posed in Jensen and Toft (Graph Coloring Problems, Wiley, New York, 1995). We also consider bounds on χS(G) when the size and genus of G are known. We also consider the parameter when applied to planar and outerplanar graphs. It is known that the problem of determining whether χS(G)⩽k is NP-complete for all k⩾2. We extend this by showing it is NP-complete for k=2 even when restricted to the class of planar triangle-free graphs with maximum degree four. As a corollary, we see that showing a planar triangle-free graph of maximum degree four has a 1-defective chromatic number of two is NP-complete, answering a question of Cowen et al. (J. Graph Theory 24(3) (1997) 205–219). We show that determining whether χS(G)⩽3 is NP-complete for planar graphs. We consider the subchromatic number of cartesian products of complete graphs and show a correspondence with a natural covering of matrices. We close by producing bounds on the subchromatic number in terms of chromatic number as well as the product of clique number with chromatic number. Sharpness for graphs with fixed clique size is discussed.