Graffiti's cut-vertex 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, and let c(G)c(G) be the number of cut-vertices of GG. Graffiti's cut-vertex conjecture.

α(G)≥1+c(G)2\alpha(G) \geq 1+\frac{c(G)}{2}

The paper verifies this inequality for the graph classes considered there using bounds on their cut-vertices and independence numbers, but the general conjecture remains open in the source.

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.