AGX's order-to-degree 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 order-to-degree conjecture.

α(G)≥v−1Δ\alpha(G)\geq\frac{v-1}{\Delta}

The source attributes this bound to AGX conjecture-making software and verifies it for the graph classes considered there, but gives no general proof or disproof.

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.