Do graphs with $\omega(G) = \chi(G)$ grow "common" as $|V|$ grows large?

Question

On the set $[n]:= \{1,\ldots,n\}$ we consider the set $${\cal P}_2([n]) = \big\{\{a,b\}: a,b \in [n], a\neq b\big\}.$$ Since $$|{\cal P}_2([n])| =2^{n \choose 2}$$ there are exactly $2^{n\choose 2}$ graphs on $n$ points.

We set the clique number $\omega(G)$ to be the largest $n$ such that the complete graph $K_n$ is a subgraph of $G$. For $n \geq 1$, let $$R_n = \{ G = ([n], E): E\in {\cal P}_2([n]) \text{ and } \omega(G) = \chi(G)\},$$ and set $q_n = \frac{R_n}{2^{n\choose 2}}$.

Does $\lim_{n\to\infty} q_n$ exist, and is its value equal to $1$?

Answer 1

I would say that this limit is zero. Most of the graphs on $n$ vertices have $\sim n^2/4$ edges. For such graph, the expected number of complete subgraphs of size $k\sim2\log_2n$ is $$ {n\choose k}\cdot \frac1{2^{k\choose 2}}\approx C\left(\frac{ne}{k2^{(k-1)/2}}\right)^k\to 0. $$ So most of our graphs have $\omega(G)\lesssim 2\log_2n$. Their complements $G^c$ also have $\sim n^2/4$ edges, and the same estimate for $\omega(G^c)$ holds. This means that most of such graphs have $\chi(G)\gtrsim n/(2\log_2n)$.

Answer 2

As @Ilya says, the limit is zero due to the asymptotic size of maximum cliques/independent sets. However, there is another way to see this using endomorphisms (homomorphisms from a graph to itself).

It is known that asymptotically almost surely the endomorphism monoid of any graph contains only the identity map. However, any graph with $\omega(G) = \chi(G)$ has an endomorphism to a maximum clique, which is clearly not an identity map. Therefore, the proportion of graphs with clique and chromatic number equal must go to zero asymptotically.

The proof of the result about the endomorphism monoid of graphs is in "Graphs and Homomorphisms" by Hell and Nesetril. I'm not sure if that is the original source though.