## Abstract

An even cycle C in a graph G is a nice cycle if G−V(C) has a perfect matching. A graph G is cycle-nice if each 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 significance of Pfaffian graphs is that the number of perfect matchings of a Pfaffian graph may be computed 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. In this paper we obtain complete characterizations of 3-connected and 2-connected claw-free graphs that are cycle-nice. Using these characterizations, we can decide if a cycle-nice 2-connected claw-free graph is Pfaffian.

Original language | English |
---|---|

Article number | 112876 |

Journal | Discrete Mathematics |

Volume | 345 |

Issue number | 7 |

DOIs | |

Publication status | Published - Jul 2022 |

## Keywords

- Claw-free graph
- Nice cycle
- Perfect matching
- Pfaffian graph

## ASJC Scopus subject areas

- Theoretical Computer Science
- Discrete Mathematics and Combinatorics