Independence Ratio

The ratio of the independence number of a graph G to its vertex count is known as the independence ratio of G (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


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.

Subject classifications