TxGraffiti's annihilation-number bound for connected graphs

From papers

Let GG be a nontrivial connected graph. Write 4α(G)44\alpha(G)4 for its independence number, 4a(G)44a(G)4 for its annihilation number, 4R(G)44R(G)4 for its residue, and 4Δ(G)44\Delta(G)4 for its maximum degree.

TxGraffiti's conjecture. One has

α(G)a(G)+R(G)Δ(G),\alpha(G) \ge \frac{a(G)+R(G)}{\Delta(G)},

and this bound is sharp.

The conjecture is open in general; it is established for regular bipartite and cubic Kőnig–Egerváry graphs. The bound is motivated by automated graph conjecturing and is sharp, for example, for the complete graph on four vertices.

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

Chakshu Gupta, “An annihilation-number Caro-Wei bound: a TxGraffiti conjecture and an independence-number bracket”, arXiv:2606.29553 (2026).

Additional references

5 papers in this index state this conjecture (2019–2026). The statement above is taken from the most recent of them; the others are arXiv:2406.19231, arXiv:2306.12917, arXiv:2104.01092, arXiv:1909.09093.

Solutions 0

No solutions have been posted yet.