← All problems

AGX's order-to-degree lower bound for the independence number

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