Timeline for Bounding chromatic number by a function of independence and clique number
Current License: CC BY-SA 3.0
3 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Feb 25, 2017 at 21:15 | comment | added | user36212 | $G(n,1/2)$ has clique number asymptotically $2\log n$, which is of the order $\log n$ (as Ben Barber points out) but the factor $2$ is important here. | |
| Feb 24, 2017 at 9:40 | comment | added | karpasi | What you wrote is untrue beacuse of the example of a random graph with probability $\frac{1}{2}$ that he gave. The chromatic number is $n/\log{n}$, and the right side in your first inequality is something like $\sqrt{n}$. | |
| Feb 23, 2017 at 22:59 | history | answered | user36212 | CC BY-SA 3.0 |