✦ LIBER ✦

On the ultimate independence ratio of a graph

✍ Scribed by Geňa Hahn; Pavol Hell; Svatopluk Poljak

Publisher: Elsevier Science
Year: 1995
Tongue: English
Weight: 479 KB
Volume: 16
Category: Article
ISSN: 0195-6698
DOI: 10.1016/0195-6698(95)90030-6

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

On the bounds for the ultimate independe

On the bounds for the ultimate independence ratio of a graph

✍ Xuding Zhu 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 416 KB

In this paper we study the ultimate independence ratio I(G) of a graph G, which is defined as the limit of the sequence of independence ratios of powers of G. We construct a graph G with ultimate independence ratio I(G) strictly between the previous known upper bound 1/zz(G) and lower bound 1/x(G).

On the independence ratio of a graph

✍ Michael O. Albertson; Joan P. Hutchinson 📂 Article 📅 1978 🏛 John Wiley and Sons 🌐 English ⚖ 318 KB

## Abstract This paper presents some recent results on lower bounds for independence ratios of graphs of positive genus and shows that in a limiting sense these graphs have the same independence ratios as do planar graphs. This last result is obtained by an application of Menger's Theorem to show t

Independence ratios of graph powers

✍ Pavol Hell; Xingxing Yu; Huishan Zhou 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 444 KB

We investigate the limiting behaviour of the independence ratio of increasing Cartesian powers of a graph.

A lower bound on the independence number

A lower bound on the independence number of a graph

✍ Jochen Harant 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 210 KB

A new lower bound on the independence number of a graph is established and an accompanying efficient algorithm constructing an independent vertex set the cardinality of which is at least this lower bound is given. (~

On the bipartite independence number of

On the bipartite independence number of a balanced bipartite graph

✍ Odile Favaron; Pedro Mago; Oscar Ordaz 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 603 KB

Venezuela Ap. 47567, Caracas Favaron, O., P. Mago and 0. Ordaz, On the bipartite independence number of a balanced bipartite graph, Discrete Mathematics 121 (1993) 55-63. The bipartite independence number GI aIp of a bipartite graph G is the maximum order of a balanced independent set of G. Let 6 b

On the ultimate normalized chromatic dif

On the ultimate normalized chromatic difference sequence of a graph

✍ Huishan Zhou 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 489 KB

For graphs G and H, the Cartesian product G × H is defined as follows: the vertex set is ## V(G) × V(H), and two vertices (g,h) and (9',h') are adjacent in G × H if either g = g' and hh' E E(H) or h = h' and g9' E E(G). Let G k denote the Cartesian product of k copies of G. The chromatic differen