Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4649334 | Discrete Mathematics | 2009 | 6 Pages |
Abstract
The Hall-ratio ρ(G)ρ(G) of a graph GG is the ratio of the number of vertices and the independence number maximized over all subgraphs of GG. The ultimate lexicographic Hall-ratio of a graph GG is defined as limn→∞ρ(G∘n)n, where G∘nG∘n denotes the nnth lexicographic power of GG (that is, nn times repeated substitution of GG into itself). Here we prove the conjecture of Simonyi stating that the ultimate lexicographic Hall-ratio equals the fractional chromatic number for all graphs.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Ágnes Tóth,