On the number of maximal independent sets in minimum colorings of split graphs

The largest number of color classes that are dominating sets (or, equivalently, maximal independent sets) among all χ(G)-colorings of a graph G is called the dominating-χ-color number of G, and denoted dχ(G). It was shown in Arumugam et al. (2011) that determining whether dχ(G)≥2 is NP-complete even in 3-chromatic graphs G. In this note, we prove that in split graphs the dominating-χ-color number equals to 1 if and only if its domination number is greater than 2. While such graphs can be efficiently recognized, we prove that for split graphs with domination number at most 2 the decision version of the problem of determining dominating-χ-color number is NP-complete. We also present existence results for split graphs attaining prescribed values of dominating-χ-color numbers and some other relevant parameters.