AGX's square-root lower bound for the independence number

From papers

Let GG be a graph, let α(G)\alpha(G) be its independence number, let vv be the number of vertices of GG, and let Δ\Delta be its maximum degree. AGX's square-root conjecture.

α(G)2vΔ\alpha(G)\geq\lceil 2\sqrt{v}\rceil-\Delta

The source attributes this conjecture to AGX conjecture-making software and verifies it for the graph classes studied there; it does not claim a general resolution.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

Boris Brimkov and Valentin Brimkov, “Graphs with degree sequence \m^m-1,n^n-1\ and \m^n,n^m\”, arXiv:2308.06670 (2023).

Solutions 0

No solutions have been posted yet.