I suspect that a topic such as this may have been considered before: if so, I hope that someone can point me to a reference on the subject.


I have a graph *G* with an upper bound *d* on its maximum degree. Define an *independent-set cover* for *G* to be a family of independent sets in *G*, whose union is *V(G)*. Is there a non-trivial upper bound for the smallest independent-set cover of *G*? [That is: I would like the number of independent sets in the family to be as small as possible; the size of any particular independent set within that family is unimportant.]


I'm also interested in the case where the degrees of the vertices may differ substantially from the maximum degree.


**Edited to add:** thanks to those who pointed out that the size of the smallest independent-set cover is just the chromatic number (by definition). I'm not sure how I managed to avoid noticing that this is what I was asking about, except that I probably think of colourings too much in terms of vertex-labellings and not often enough in terms of vertex partitions.



Covering of a graph via independent sets
As has already been pointed out, this is the chromatic number $\chi$. (For example, the assertion that all planar graphs have $ \chi \le 4$ is the famous "Four color theorem.")


You say your graph has maximum degree $d$. Then in all cases $\chi \le d+1$, and [Brooks' theorem](http://en.wikipedia.org/wiki/Brooks%2527_theorem) gives that in fact $\chi \le d$ as long as $G$ is not a complete graph or an odd cycle. 


