Characterizing and generalizing cycle completable graphs

Maria Chudnovsky; Ian M.J. McInnis

doi:10.1016/j.disc.2023.113754

Characterizing and generalizing cycle completable graphs

Maria Chudnovsky, Ian M.J. McInnis

Mathematics

Research output: Contribution to journal › Article › peer-review

Abstract

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 language	English (US)
Article number	113754
Journal	Discrete Mathematics
Volume	347
Issue number	2
DOIs	https://doi.org/10.1016/j.disc.2023.113754
State	Published - Feb 2024

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Discrete Mathematics and Combinatorics

Keywords

Cycle completable
Forbidden induced subgraphs
k-quasichordal

Access to Document

10.1016/j.disc.2023.113754

Cite this

@article{48c6f9edf7534d94924da538e1b9c373,

title = "Characterizing and generalizing cycle completable graphs",

abstract = "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.",

keywords = "Cycle completable, Forbidden induced subgraphs, k-quasichordal",

author = "Maria Chudnovsky and McInnis, {Ian M.J.}",

note = "Publisher Copyright: {\textcopyright} 2023 Elsevier B.V.",

year = "2024",

month = feb,

doi = "10.1016/j.disc.2023.113754",

language = "English (US)",

volume = "347",

journal = "Discrete Mathematics",

issn = "0012-365X",

publisher = "Elsevier B.V.",

number = "2",

}

TY - JOUR

T1 - Characterizing and generalizing cycle completable graphs

AU - Chudnovsky, Maria

AU - McInnis, Ian M.J.

PY - 2024/2

Y1 - 2024/2

N2 - 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.

AB - 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.

KW - Cycle completable

KW - Forbidden induced subgraphs

KW - k-quasichordal

UR - http://www.scopus.com/inward/record.url?scp=85174456468&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85174456468&partnerID=8YFLogxK

U2 - 10.1016/j.disc.2023.113754

DO - 10.1016/j.disc.2023.113754

M3 - Article

AN - SCOPUS:85174456468

SN - 0012-365X

VL - 347

JO - Discrete Mathematics

JF - Discrete Mathematics

IS - 2

M1 - 113754

ER -

Characterizing and generalizing cycle completable graphs

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this