On the ultimate independence ratio of a graph (Q1893949): Difference between revisions

The ultimate independence ratio \(I(G)\) of a graph \(G\) is the limit, as \(k \to \infty\), of the sequence of independence ratios of the (box) powers \(G^k\). It is shown that \(I(H)\leq I(G)\) whenever there is a graph homomorphism from \(G\) to \(H\). Using this monotony property, it is 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\). This result yields a number of consequences; in particular, exact values of \(I(G)\) are computed for several classes of graphs (e.g., \(I(G) = 1/2\) if \(G\) is bipartite).