Friday, 16 March 2012

co.combinatorics - Covering of a graph via independent sets

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 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 minimum-size 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.

No comments:

Post a Comment