1
$\begingroup$

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.

Improve this question
$\endgroup$

4 Answers 4

Reset to default
7
$\begingroup$

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.

Improve this answer
$\endgroup$
7
$\begingroup$

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.

Improve this answer
$\endgroup$
3
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thanks, Tony. Unfortunately, in the problem setting I'm looking at, it is unlikely to be feasible to find the maximum clique. $\endgroup$
    – Niel de Beaudrap
    Commented Sep 4, 2010 at 10:09
0
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – Niel de Beaudrap
    Commented Sep 6, 2010 at 13:04
  • $\begingroup$ 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 $\endgroup$
    – Andrew D. King
    Commented Sep 6, 2010 at 21:12

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .