4
$\begingroup$

For a graph $G$, let $\omega(G)$ and $\alpha(G)$ denoted the clique and independence numbers of $G$ respectively. For some families of graphs, e.g. vertex transitive graphs, it is known that $\alpha(G)\omega(G) \le |V(G)|$ and this is usually referred to as the "clique-coclique bound" ('coclique' is another name for independent set).

In my answer to this question, I remarked that for all the families that I know of, the clique-coclique bound follows from the stronger fact that $\vartheta(G)\vartheta(\bar{G}) \le |V(G)|$ holds (in fact you have equality because the other inequality always holds). Here, $\vartheta$ denotes the Lovasz theta number, and $\bar{G}$ denotes the complement of $G$. This is indeed stronger due to the famous "Sandwich Theorem" stating that $\omega(G) \le \vartheta(\bar{G}) \le \chi(G)$ for all graphs $G$.

Having said that, I am now curious as to how true it really is. So I have the following question:

Is there any (natural) family of graphs for which it is known that the clique-coclique bound holds but it is not known that $\vartheta(G)\vartheta(\bar{G}) = |V(G)|$ for all $G$ in the family?

I include the word "natural" because there are graphs $G$ for which the clique-coclique bound holds but $\vartheta(G)\vartheta(\bar{G}) > |V(G)|$, so of course I can just consider the family of all such graphs.

More generally though, I am interested in what are the known families of graphs for which the clique-coclique bound holds. The main families that I know of are the following:

  1. Vertex transitive graphs;
  2. Graphs that are unions of classes of an association scheme;
  3. Graphs that are unions of classes of a homogeneous coherent configuration;
  4. 1-walk-regular graphs (and their complements).

In fact families 1 and 2 are contained in family 3, so the list could have been half as long. It is also not hard to show that a bipartite graph satisfies the clique-coclique bound if and only if it has a perfect matching, in which case it meets the bound with equality and one also has that $\chi(G)\chi(\bar{G}) = |V(G)|$ (which is even stronger than the Lovasz theta inequality).

Are there any other families known that are not covered by the above?

The most general family I know of (which uses some unpublished work), is the family of graphs whose partially coherent algebras are homogeneous (contain only matrices of constant diagonal). The partially coherent algebra of a graph $G$ with adjacency matrix $A$ is the smallest subalgebra of the $|V(G)| \times |V(G)|$ complex matrices which contains the identity and the all ones matrix, is closed under conjugate transposition, and closed under Schur (entrywise) product when one of the two factors involved is either $I$ or $A$. I gave a brief explanation of why graphs with homogeneous partially coherent algebras satisfy the clique-coclique bound in my answer to the above mentioned question. This family subsumes all of the above families, except the bipartite graphs with perfect matchings (and their complements). I'd be interested to know if there is any family of graphs not contained in this one for which the clique-coclique bound holds.

I guess what I am wondering is to what extent is the clique-coclique bound merely a consequence of $\vartheta(G)\vartheta(\bar{G}) \le |V(G)|$ being true?

Improve this question
$\endgroup$
7
  • $\begingroup$ Perhaps not so "natural" but because it is what I am thinking about right now: edge-critical (aka. $\alpha$-critical) triangle-free graphs. $\endgroup$
    – Oliver Krüger
    Commented Jan 5, 2018 at 13:08
  • $\begingroup$ @OliverKrüger Are you assuming connectedness? Because otherwise it seems I could add a bunch of isolated vertices to violate the clique-coclique bound. $\endgroup$
    – David Roberson
    Commented Jan 5, 2018 at 14:28
  • $\begingroup$ @DavidERobertson Oh sorry, yes I am (in fact I was thinking of "quasi-regularizable" (as Berge calles them), which includes all $\alpha$-critical graphs without $K_2$- or $K_1$-components). $\endgroup$
    – Oliver Krüger
    Commented Jan 9, 2018 at 14:14
  • 1
    $\begingroup$ @DavidERoberson All such graphs have α(G)≤n(G)/2 (in fact, |S|≤|N(S)| for all independent sets S see e.g. [1, Theorem 2] for quasi-regularizable graphs). For α-critical graphs it can be seen to be equivalent to the non-negativity of the so called Gallai class number. Reference: [1] Berge C. (1981) Some common properties for regularizable graphs, edge-critical graphs and b-graphs. In: Saito N., Nishizeki T. (eds) Graph Theory and Algorithms. Lecture Notes in Computer Science, vol 108. $\endgroup$
    – Oliver Krüger
    Commented Jan 10, 2018 at 9:25
  • 1
    $\begingroup$ @DavidERoberson This class (when also imposing triangle-freeness) is not completely artificial since it naturally shows up in the study of edge-minimal (Ramsey) graphs that are related to the Ramsey numbers of the form R(3,t). $\endgroup$
    – Oliver Krüger
    Commented Jan 10, 2018 at 9:26

0

Reset to default

You must log in to answer this question.