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

Hi,

Let G be a connected graph without loops. The (vertex) independence number is the size of the maximal set of vertices such that no two vertices in the set are connected by an edge. The (vertex) clique cover number is the minimal number of cliques in G which cover all the vertices of G (not necessarily all the edges of G).

My question is - under what conditions are those two numbers equal?

share|improve this question
    
The question might be better expressed as "When does the independence number of a graph equal the clique cover number?" or "When is the independence number of a graph equal to the independence number?". –  András Salamon Jul 25 '10 at 21:42
add comment

3 Answers

This seems related to perfect graphs, since your property is equivalent to asking that the complement graph $G'$ has coinciding chromatic and clique numbers. Since Lovasz perfect graph theorem (1972) says that the complement of a perfect graph is perfect, if $G$ is perfect it satisfies your property, as well as all its induced subgraphs. But I doubt that this is a necessary condition.

EDIT (in response to F. Dorais's comment) : Particularly striking in this context is the recent solution of the 40 years old C. Berge Strong Perfect Graph conjecture (in 2002) by Chudnovsky, Robertson, Seymour and Thomas, that says that a graph is perfect if (and only if) no induced subgraph is an odd cycle of length at least 5 or the complement of such a cycle (the only if part is elementary).

share|improve this answer
    
+1: It's probably a good idea to add a few words on the more recent Strong Perfect Graph Theorem - en.wikipedia.org/wiki/… –  François G. Dorais Jul 24 '10 at 14:14
add comment

As BS pointed out, by the perfect graph theorem, being perfect (nicely characterized by the strong perfect graph theorem) is a sufficient condition for what you want. However it is certainly not necessary. Take for instance the disjoint union of the complete graph on 3 vertices and an odd cycle with at least 5 elements. The graph is not perfect but has chromatic number 3 and clique number 3. Its complement is connected, not perfect (again by the perfect graph theorem), and has vertex independence number equal to the least size of a cover by cliques.

This (pathological) example shows that it might be difficult to come up with reasonable conditions that are both necessary and sufficient. This example also shows why the focus has been on perfect graphs, i.e., (by the perfect graph theorem) graphs that have your property hereditarily (for all induced subgraphs).

share|improve this answer
add comment

Denote the independence number of $G$ by $\alpha(G)$, and the clique cover number by $\overline{\chi}(G)$. It is obvious that $\overline{\chi}(G) \ge \alpha(G)$. You are asking when $\alpha(G) = \overline{\chi}(G)$.

This seems to be the question that drove the definition and investigation of perfect graphs. See Berge's historical overview. The definition of perfect graphs requires the equality between independence number and clique cover number for every induced subgraph. This is Berge's "Beautiful Property", defining what he calls "class 2". Rephrasing a comment by Lovász, the induced subgraph condition is needed to remove the artificial examples where a large set $X$ of new vertices is added to a graph such that each vertex in $X$ is adjacent to each vertex of the original graph. Applying this construction to any graph yields a new graph that satisfies your condition.

Berge also defined "class 3", those graphs for which the chromatic number equals the clique number for every induced subgraph, and "class 4", the graphs which contain no induced odd hole or induced odd antihole. In the paper mentioned above, Lovász proved the perfect graph theorem, that the complement of a perfect graph is perfect. This shows that "class 2" and "class 3" are the same. Perfect graphs are now usually defined as "class 3", and the strong perfect graph theorem shows that "class 4", of Berge graphs, is the same as "class 3". Berge claimed he was originally more interested in whether "class 2" and "class 3" coincided.

One final remark: if $\alpha(G) = \overline{\chi}(G)$, then the Shannon capacity of $G$ is $\log \alpha(G)$. This is Berge's "class 1" (note that the "log" is missing in the paper, clearly a typo). This is really saying that in the limit, when $\alpha(G) = \overline{\chi}(G)$ then the independence number dominates the channel performance in the long run. From this applied point of view, it makes sense to look for the kinds of graphs which have this property inherently, and not just by a large independent set being glued on.

However, there may be other applications for graphs for which $\alpha(G) = \overline{\chi}(G)$ holds, but where this relationship fails for some induced subgraphs. This would then make it interesting to find the graphs that have this property but not via a glued-on independent set. To end this answer on a question: do you have such an application in mind?

share|improve this answer
    
The answer to your question is that I don't know if the graphs I'm studying are perfect. Yesterday I understood that my graphs are actually incidence geometries (when you think about cliques as lines). –  Izhar Oppenheim Jul 26 '10 at 7:03
    
That sounds like gridline graphs, which are a quite well-behaved subclass of perfect graphs: dx.doi.org/10.1016/S0166-218X(02)00200-7 –  András Salamon Jul 27 '10 at 17:53
    
Thanks for the reference! I would be very happy if it turns out my graph is perfect. –  Izhar Oppenheim Jul 28 '10 at 16:47
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.