Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
add comment

4 Answers

up vote 6 down vote accepted

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 gives that in fact $\chi \le d$ as long as $G$ is not a complete graph or an odd cycle.

share|improve this answer
add comment

If you further specify the class of graphs you're looking at, it may be possible to get a much better bound. As it is, you cannot really do better than $\Delta+1$ in terms of very easily computable bounds, as mentioned above.

share|improve this answer
    
The setting which I'm looking at puts on very few obvious restrictions on the class of graphs I'm looking at. I'm in fact looking at the generalization of the line graph to hypergraphs; so what I'm after would actually be something like the hyper-edge-chromatic number of a hypergraph. I may ask a separate question about that soon. –  Niel de Beaudrap Sep 6 '10 at 13:04
    
In that case I would consider how to ask the question in terms of hypergraphs and ask a question in this context. I'm confident somebody will know a better bound than $\Delta+1$. See, for example, this conjecture: garden.irmacs.sfu.ca/?q=op/a_generalization_of_vizings_theorem –  Andrew D. King Sep 6 '10 at 21:12
add comment

Since you mentioned that you have a bound on the maximum degree of your graph, you might also want to look at Reed's Conjecture, which states that for any graph $G$,

$\chi(G) \leq \lceil \frac{\Delta (G) + \omega (G) +1}{2}\rceil$.

Here, $\chi$ is the chromatic number, $\Delta$ is the maximum degree, and $\omega$ is the maximum clique number.

share|improve this answer
    
Thanks, Tony. Unfortunately, in the problem setting I'm looking at, it is unlikely to be feasible to find the maximum clique. –  Niel de Beaudrap Sep 4 '10 at 10:09
add comment

The number that you are considering is the chromatic number of a graph. A lower bound is the largest size of a clique. This number features in some of the most discussed theorems of graph theory, the perfect graph theorem and the strong perfect graph theorem.

A graph is perfect if every induced subgraph has chromatic number equal maximal clique size.

You will find plenty of material if you search for chromatic number.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.