Sum-perfect graphs

Bart Litjens, Sven C. Polak, Vaidy Sivaraman

Research output: Contribution to journalArticleScientificpeer-review

34 Downloads (Pure)

Abstract

Inspired by a famous characterization of perfect graphs due to Lovász, we define a graph
G to be sum-perfect if for every induced subgraph H of G, α(H) + ω(H) ≥ |V(H)|. (Here α
and ω denote the stability number and clique number, respectively.) We give a set of 27
graphs and we prove that a graph G is sum-perfect if and only if G does not contain any of
the graphs in the set as an induced subgraph.
Original languageUndefined/Unknown
Pages (from-to)232-239
Number of pages8
JournalDiscrete Applied Mathematics
Volume259
DOIs
Publication statusPublished - 2019
Externally publishedYes

Cite this