加载中…
For c in [0,1] let P_n© denote the set of n-vertex perfect graphs with density c and C_n© the set of n-vertex graphs without induced C_5 and with density c. We show that log|P_n©|/binom{n}{2}=log|C_n©|/binom{n}{2}=h©+o(1) with h©=1/2 if 1/4<c<3/4 and h©=H(|2c-1|)/2 otherwise, where H is the binary entropy function. Further, we use this result to deduce that almost all graphs in C_n© have homogenous sets of linear size. This answers a question raised by Loebl, Reed, Scott, Thomason, and Thomass'e [Almost all H-free graphs have the Erd\H{o}s-Hajnal property] in the case of forbidden induced C_5.

生成讲解博客的中文版本

生成AI智能校验的中文版本