On the ultimate independence ratio of a graph
type: Item
instance of: scholarly article
title: On the ultimate independence ratio of a graph
zbMATH Open document ID: 0829.05026
DOI: 10.1016/0195-6698(95)90030-6
author: Geňa Hahn
author: Svatopluk Poljak
author: Pavol Hell
published in: European Journal of Combinatorics
publication date: 1996-01-07T00:00:00Z
review text: The ultimate independence ratio \(I(G)\) of a graph \(G\) is the limit, as \(k \to \infty\), of the sequence of independence ratios of the (box) powers \(G^k\). It is shown that \(I(H)\leq I(G)\) whenever there is a graph homomorphism from \(G\) to \(H\). Using this monotony property, it is 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\). This result yields a number of consequences; in particular, exact values of \(I(G)\) are computed for several classes of graphs (e.g., \(I(G) = 1/2\) if \(G\) is bipartite).
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 05C35
Mathematics Subject Classification ID: 05C25
zbMATH DE Number: 773829
zbMATH Keywords: independence number
zbMATH Keywords: chromatic number
zbMATH Keywords: ultimate independence ratio
zbMATH Keywords: graph homomorphism
zbMATH Keywords: fractional chromatic numbers
reviewed by: Jozef Širáň
MaRDI profile type: Publication
full work available at URL: 0195-6698(95)90030-6
OpenAlex ID: W1979898269
cites work: The chromatic difference sequence of a graph
cites work: Homomorphisms of 3-chromatic graphs
cites work: Q4848762
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: On a Problem of C. E. Shannon in Graph Theory
cites work: The chromatic difference sequence of the Cartesian product of graphs
cites work: On the bounds for the ultimate independence ratio of a graph
description: scientific article; zbMATH DE number 773829