On the bounds for the ultimate independence ratio of a graph (Q1923515)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On the bounds for the ultimate independence ratio of a graph |
scientific article |
Statements
On the bounds for the ultimate independence ratio of a graph (English)
0 references
7 October 1996
0 references
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\).
0 references
independent set
0 references
independence ratio
0 references
independence number
0 references
ultimate independence
0 references
Cartesian product
0 references
fractional chromatic number
0 references
star chromatic number
0 references