×

On the ultimate independence ratio of a graph. (English) Zbl 0829.05026

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).

MSC:

05C15 Coloring of graphs and hypergraphs
05C35 Extremal problems in graph theory
05C25 Graphs and abstract algebra (groups, rings, fields, etc.)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Albertson, M. O.; Berman, D. M., The chromatic difference of a graph, J. Combin. Theory, Ser. B, 29, 1-12 (1980) · Zbl 0377.05020
[2] Albertson, M. O.; Collins, K. L., Homomorphisms of 3-chromatic graphs, Discr. Math., 54, 127-132 (1985) · Zbl 0572.05024
[3] G. Hahn and J. Širáň, A note on intersecting cliques in Cayley graphs, J. Combin. Math. Comb. Comp.; G. Hahn and J. Širáň, A note on intersecting cliques in Cayley graphs, J. Combin. Math. Comb. Comp. · Zbl 0832.05051
[4] Hell, P.; Roberts, F., Analogues of the Shannon capacity of a graph, Ann. Discr. Math., 12, 155-168 (1982) · Zbl 0501.05035
[5] Hell, P.; Yu, X.; Zhou, H., Independence ratios of graph powers, Ann. Discr. Math., 127, 213-220 (1994) · Zbl 0795.05054
[6] Hwang, S. F.; Hsu, L. H., Capacity equivalent class for graphs with fixed odd girth, Tamkang J. Math., 20, 159-167 (1989) · Zbl 0688.05068
[7] Lovász, L., On the Shannon capacity of a graph, IEEE Trans. Inform. Theory, IT-25, 1-7 (1979) · Zbl 0395.94021
[8] Rosenfeld, M., On a problem of Shannon in graph theory, (Proc. Am. Math. Soc., 18 (1967)), 315-319 · Zbl 0147.42801
[9] Shannon, C. E., The zero-error capacity of a noisy channel, IRE Trans. Inform. Theory, 2, 8-19 (1956)
[10] Zhou, H., Homomorphism properties of graph products, (Ph.D. thesis (1988), Simon Fraser University)
[11] Zhou, H., The chromatic difference sequence of the cartesian product of graphs, Discr. Math., 90, 297-311 (1991) · Zbl 0734.05046
[12] X. Zhu, On the bounds for the ultimate independence ratio of a graph, Discr. Math.; X. Zhu, On the bounds for the ultimate independence ratio of a graph, Discr. Math. · Zbl 0857.05049
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.