The TxGraffiti zero forcing versus independence conjecture for subcubic graphs

From papers

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.

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

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

Solutions 0

No solutions have been posted yet.