8
$\begingroup$

Let G be a connected graph without loops. The (vertex) independence number is the maximum size of a set of vertices such that no two vertices in the set are connected by an edge. The (vertex) clique cover number is the minimum 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?

$\endgroup$
1
  • $\begingroup$ fort such graphs computing $\alpha(G)$ will be easy, as it's Lovasz $\theta(G)$ (or of the complement of $G$, depending upon its definition. $\endgroup$ Mar 5, 2016 at 19:23

3 Answers 3

7
$\begingroup$

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).

$\endgroup$
0
7
$\begingroup$

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?

$\endgroup$
3
  • $\begingroup$ 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). $\endgroup$ Jul 26, 2010 at 7:03
  • $\begingroup$ 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 $\endgroup$ Jul 27, 2010 at 17:53
  • $\begingroup$ Thanks for the reference! I would be very happy if it turns out my graph is perfect. $\endgroup$ Jul 28, 2010 at 16:47
6
$\begingroup$

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).

$\endgroup$
1

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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