No, Bob would not have committed fraud. And to resolve the issue, all you'd have to do is invite people to come in and see for themselves. Assuming that it was, in fact, a case of libel or slander, people will know that Bob is a liar, and he won't be trusted anymore. His customers will wonder why, if his business is worth anything, he would have had to tell such lies. And thereafter people will tend to choose your business over Bob's. Problem solved without anybody throwing a temper tantrum and starting a fight.
Or it could go to third party dispute resolution: You appeal the charge to a well-respected restaurant inspecting agency, and after investigating, they issue you a Certificate of Cleanliness and publish the fact that Bob had lied about you. Different means, same results. You have far too narrow a view of how the market would solve such problems. Dispute resolution need not involve the use of force to obtain restitution.
Also, you are using the legal definition of fraud, which is not the sense in which libertarian theorists have used it. Just as the legal definition of "theft" does not include taxation. For a libertarian to consider something a crime, some invasion of property rights must have occurred. And as one does not own one's reputation, telling lies about another person cannot be considered a crime.