Zero Forcing versus Independence in Subcubic Graphs
Is the zero forcing number of every connected graph with maximum degree at most its independence number plus one? A connected 24-vertex subcubic graph with independence number and zero forcing number refutes this 2017 TxGraffiti conjecture, and a 36-vertex cubic variant refutes the cubic form: is attained.
- Result
- Disproved
- Status
- Resolved
- AI contribution
- AI-discovered
- Method
- Construction
- Field
- Graph theory
- Posed by
- TxGraffiti (automated conjecturing program)
- Year posed
- 2017
- Years open
- 9y
- Solved
- 2026-07-26
- Model
- Claude Opus 5
- Vendor
- Anthropic
- Collaborators
- Mikko Fischer
- Verification
- Unreviewed
- Publication
- Preprint
- Significance
- 5 / 100
- Disclosed cost
- —
- Wikipedia
- No dedicated article
What the AI did
The counterexamples were found with the assistance of Claude Opus 5, directed by the author, who independently verified them - a conjecture generated by one automated system falling to a search assisted by another.
Verification
Explicit finite counterexamples, independently checked by the author; arXiv preprint, not yet peer-reviewed.