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.
All Science Journal Classification (ASJC) codes
- Theoretical Computer Science
- Discrete Mathematics and Combinatorics
- Cycle completable
- Forbidden induced subgraphs