Characterizing and generalizing cycle completable graphs

Maria Chudnovsky, Ian M.J. McInnis

Research output: Contribution to journalArticlepeer-review


The family of cycle completable graphs has several cryptomorphic descriptions, the equivalence of which has heretofore been proven by a laborious implication-cycle that detours through a motivating matrix completion problem. We give a concise proof, partially by introducing a new characterization. Then we generalize this family to “k-quasichordal” graphs, with three natural characterizations.

Original languageEnglish (US)
Article number113754
JournalDiscrete Mathematics
Issue number2
StatePublished - Feb 2024

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics


  • Cycle completable
  • Forbidden induced subgraphs
  • k-quasichordal


Dive into the research topics of 'Characterizing and generalizing cycle completable graphs'. Together they form a unique fingerprint.

Cite this