On cycle-nice claw-free graphs

Shanshan Zhang, Xiumei Wang, Jinjiang Yuan, C. T. Ng, T. C.E. Cheng

Research output: Journal article publicationJournal articleAcademic researchpeer-review

1 Citation (Scopus)


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 languageEnglish
Article number112876
JournalDiscrete Mathematics
Issue number7
Publication statusPublished - Jul 2022


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

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics


Dive into the research topics of 'On cycle-nice claw-free graphs'. Together they form a unique fingerprint.

Cite this