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

About 3 years old · traced to

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.

References

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).

Progress summary

Never refreshed

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

Solutions 0

No solutions have been posted yet.