THE ULTIMATE CATEGORICAL INDEPENDENCE RATIO OF COMPLETE MULTIPARTITE GRAPHS

The independence ratio i(G) of a graph G is the ratio of its independence number and the number of vertices. The ultimate categorical independence ratio of a graph G is defined as lim(k -> 8) i(G(xk)), where G(xk) denotes the kth categorical power of G. This parameter was introduced by Brown, Nowakowski, and Rall, who asked about its value for complete multipartite graphs. In this paper we determine the ultimate categorical independence ratio of complete multipartite graphs.