On cycle-nice claw-free graphs (Q2138970)

By a nice cycle of a graph $G$, we mean an even cycle $C$ such that $G-V(C)$ has a perfect matching. A graph $G$ is cycle-nice if every even cycle in $G$ is a nice cycle. An even cycle $C$ in an orientation of a graph $G$ is clockwise odd if the number of its edges directed in the clockwise sense is odd. A graph $G$ is Pfaffian if there is an orientation of $G$ such that each nice cycle of $G$ is clockwise odd. The importance of Pfaffian graphs is that the number of perfect matchings of a Pfaffian graph may be determined in polynomial time. Clearly, if $G$ is a cycle-nice graph, then $G$ is Pfaffian if and only if $G$ admits an orientation such that each even cycle in $G$ is clockwise odd. The authors here obtained a complete characterization of 3-connected and 2-connected claw-free graphs that are cycle-nice. They then used these characterizations to decide if a cycle-nice 2-connected claw-free graph is Pfaffian. The concept is very deep and the proof techniques are mind-blowing.