The average size of an independent set in graphs with a given chromatic number (Q1081615): Difference between revisions

Let G be a graph on n vertices, let \(\chi\) (G) denote its chromatic number, and let \(\alpha\) (G) denote the average size of an independent set of verties of G. A simple argument shows that \(\alpha (G)=\Omega (n/\chi (G)\log \chi (G))\). Here we show that this is sharp by constructing, for every \(\chi\leq O(n/\log n)\) a graph G with \(\chi (G)=\chi\) and with \(\alpha (G)=\Theta (n/\chi \log \chi)\). This settles a problem of Linial and Saks.