On the bounds for the ultimate independence ratio of a graph
type: Item
instance of: scholarly article
title: On the bounds for the ultimate independence ratio of a graph
zbMATH Open document ID: 0857.05049
DOI: 10.1016/0012-365X(93)E0171-Y
published in: Discrete Mathematics
publication date: 1996-10-07T00:00:00Z
review text: 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\).
Mathematics Subject Classification ID: 05C35
zbMATH DE Number: 932558
zbMATH Keywords: independent set
zbMATH Keywords: independence ratio
zbMATH Keywords: independence number
zbMATH Keywords: ultimate independence
zbMATH Keywords: Cartesian product
zbMATH Keywords: fractional chromatic number
zbMATH Keywords: star chromatic number
author: Xuding Zhu
reviewed by: Jozef Širáň
MaRDI profile type: Publication
cites work: The chromatic difference sequence of a graph
cites work: Homomorphisms of 3-chromatic graphs
cites work: A note on the star chromatic number
cites work: On the ultimate independence ratio of a graph
cites work: Analogues of the Shannon Capacity of a Graph
cites work: Independence ratios of graph powers
cites work: Q4206781
cites work: On the Shannon capacity of a graph
cites work: Star chromatic number
cites work: The chromatic difference sequence of the Cartesian product of graphs
cites work: Star chromatic numbers and products of graphs
description: scientific article; zbMATH DE number 932558