My wife abandoned my kids and me mid July, 2014. For 2014 the option of "Head of Household" was not available as the IRS says that the spouse has to not have lived with you for the last 6 months of the year to be "considered unmarried", so we ended up filing as "Married Filing Jointly". For 2015, "Head of Household" is available to me, however I don't know how to tell her to file. Is she then single, or Married filing separately?
She is still married, so she cannot file as "Single" under any circumstances. If the two of you cannot agree to file as "Married Filing Jointly", then neither of you can file as "Married Filing Jointly".
Usually the only choice left for her is "Married Filing Separately". If she has a dependent in her household, she can also file as "Head of Household". If she also tries to claim the kids as her dependents, then the IRS will adjudicate which one of you has the right to claim the dependents, and, if the situation is as you describe, they will deny her claim to those dependents. She may or may not have other dependents that she can rightfully claim.