The TxGraffiti zero forcing versus independence conjecture for subcubic graphs

Less than 1 year old · traced to

Let GG be a connected graph, let Δ(G)\Delta(G) denote its maximum degree, let Z⁡(G)\operatorname{Z}(G) denote its zero forcing number, and let α(G)\alpha(G) denote its independence number.

TxGraffiti's conjecture. If G≇K4G \not\cong K_4 and Δ(G)≤3\Delta(G)\leq 3, then

Z⁡(G)≤α(G)+1.\operatorname{Z}(G)\leq \alpha(G)+1.

The conjecture was proposed for connected graphs of maximum degree at most 33. It is refuted by both a connected subcubic graph and a connected cubic graph: the former has α(G)=9\alpha(G)=9 and Z⁡(G)=11\operatorname{Z}(G)=11, while the latter has α(G)=15\alpha(G)=15 and Z⁡(G)=17\operatorname{Z}(G)=17, so the claimed bound fails in each case.

References

Primary source

Mikko Fischer, “A counterexample to the zero forcing versus independence conjecture for cubic and subcubic graphs”, arXiv:2607.23664 (2026).

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.