On the bounds for the ultimate independence ratio of a graph (Q1923515): Difference between revisions

The independence ratio \(i(G)\) of a graph \(G\) is defined as \(i(G)=\alpha(G)/|V(G)|\), where \(\alpha(G)\) is the independence number of \(G\). The ultimate independence ratio of \(G\) is the limit \(I(G)=\lim_{k\to\infty} i(G^k)\), where \(G^k\) denotes the Cartesian product of \(k\) copies of \(G\). Hahn, Hell and Poljak [Eur. J. Comb., to appear] proved that \(1/\chi(G)\leq I(G)\leq 1/\chi_f(G)\), where \(\chi(G)\) and \(\chi_f(G)\) are the chromatic and the fractional chromatic number of \(G\), respectively. In the paper, a graph \(G\) is constructed for which both the above inequalities are strict. Moreover, the lower bound on \(I(G)\) is improved to \(1/\chi^*(G)\leq I(G)\), where \(\chi^*(G)\) is the star chromatic number of \(G\).