  An invaluable method for probing the physics of a quantum many-body spin
system is a mapping to noninteracting effective fermions. We find such mappings
using only the frustration graph $G$ of a Hamiltonian $H$, i.e., the network of
anticommutation relations between the Pauli terms in $H$ in a given basis.
Specifically, when $G$ is (even-hole, claw)-free, we construct an explicit
free-fermion solution for $H$ using only this structure of $G$, even when no
Jordan-Wigner transformation exists. The solution method is generic in that it
applies for any values of the couplings. This mapping generalizes both the
classic Lieb-Schultz-Mattis solution of the XY model and an exact solution of a
spin chain recently given by Fendley, dubbed "free fermions in disguise." Like
Fendley's original example, the free-fermion operators that solve the model are
generally highly nonlinear and nonlocal, but can nonetheless be found
explicitly using a transfer operator defined in terms of the independent sets
of $G$. The associated single-particle energies are calculated using the roots
of the independence polynomial of $G$, which are guaranteed to be real by a
result of Chudnovsky and Seymour. Furthermore, recognizing (even-hole,
claw)-free graphs can be done in polynomial time, so recognizing when a spin
model is solvable in this way is efficient. We give several example families of
solvable models for which no Jordan-Wigner solution exists, and we give a
detailed analysis of such a spin chain having 4-body couplings using this
method.
