A sharp bound on the binding number of -free graphs and the Brandt conjecture
In the authors' words
The binding number of a graph is the smallest ratio among all nonempty vertex sets whose neighborhood is not the whole vertex set. We prove that every finite nonempty -free graph has binding number at most for every , confirming Brandt's conjecture; the bound is sharp for complete -partite graphs with equal nonempty parts. We first prove the case and then extend it to all by induction.
Main resultThe abstract does not state a limitation.
Appeared: Wednesday, October 21. arXiv. Preprint, not yet peer-reviewed.
Authors' comment: 12 pages