TOPICS
Search

Independence Ratio

The independence ratio of a graph G is the ratio of its independence number to the vertex count of G (Bollobás 1981).

The product of the chromatic number and independence ratio of a graph is at least 1 (Bollobás 1981).

Dúcz and Varga (2026) constructed the snail graph and used it to prove the existence of a finite unit-distance graph G with alpha(G)/|G|<1/4, answering in the negative Erdős's question whether every such graph has independence ratio at least 1/4. ChatGPT and Codex assisted the computational search and software development, while the authors state that they conceived and verified the mathematical arguments. Independent peer review had not been reported as of Sep. 21, 2026 (Dúcz and Varga 2026, VibeMathed 2026).

Precomputed independence numbers for many named graphs can be obtained in the Wolfram Language using GraphData[graph, "IndependenceRatio"].

See also

Fractional Chromatic Number, Independence Number, Independence Polynomial, Independent Set, Matching Number, Snail Graph, Unit-Distance Graph

Explore with Wolfram|Alpha

References

Bollobás, B. "The Independence Ratio of Regular Graphs." Proc. Amer. Math. Soc. 83, 433-436, 1981.Dúcz, A. and Varga, D. "A Unit-Distance Graph in the Plane with Independence Ratio Below 1/4." 26 Jun 2026. https://arxiv.org/abs/2606.28157.VibeMathed. "Erdős's Question on the Independence Ratio of Unit-Distance Graphs." 26 Jun 2026. https://vibemathed.com/problem/unit-distance-independence-ratio.

Referenced on Wolfram|Alpha

Independence Ratio

Cite this as:

Weisstein, Eric W. "Independence Ratio." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/IndependenceRatio.html

Subject classifications