On the ultimate lexicographic Hall-ratio

AbstractThe Hall-ratio ρ(G) of a graph G is the ratio of the number of vertices and the independence number maximized over all subgraphs of G. The ultimate lexicographic Hall-ratio of a graph G is defined as limn→∞ρ(G∘n)n, where G∘n denotes the nth lexicographic power of G (that is, n times repeated substitution of G into itself). Here we prove the conjecture of Simonyi stating that the ultimate lexicographic Hall-ratio equals the fractional chromatic number for all graphs