The ratio of the independence number of a graph
to its vertex count is known as the independence
ratio of
(Bollobás 1981).
The product of the chromatic number and independence
ratio of a graph is at least 1 (Bollobás 1981).
Precomputed independence numbers for many named graphs can be obtained in the Wolfram Language using GraphData[graph,
"IndependenceRatio"].
See also
Independence Number,
Independence Polynomial,
Independent Set,
Matching
Number
Explore with Wolfram|Alpha
References
Bollobás, B. "The Independence Ratio of Regular
Graphs." Proc. Amer. Math. Soc. 83, 433-436, 1981.
Cite this as:
Weisstein, Eric W. "Independence Ratio."
From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/IndependenceRatio.html
Subject classifications