Sum-perfect graphs

DOI10.1016/J.DAM.2018.12.015MaRDI QIDQ1735702zbMATH OpenOpenAlexFDO

Authors Bart Litjens, Vaidy Sivaraman, Sven C. Polak

Publication date 28 March 2019

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1710.07546, https://ir.cwi.nl/pub/30363

zbMATH Keywords

cliqueperfect graphstable setforbidden induced subgraphsum-perfect graph

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Perfect graphs (05C17)

Abstract: Inspired by a famous characterization of perfect graphs due to Lov'{a}sz, we define a graph $G$ to be sum-perfect if for every induced subgraph $H$ of $G$, $alpha(H)+omega(H)geq|V(H)|$. (Here $alpha$ and $omega$ 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.

Recommendations

• A new characterization of perfect graphs
• On perfectness of sums of graphs
• Progress on perfect graphs
• A note on perfect graphs
• Perfect graphs

Cites work

• scientific article; zbMATH DE number 3889565 (Why is no real title available?)
• scientific article; zbMATH DE number 3445275 (Why is no real title available?)
• scientific article; zbMATH DE number 1445284 (Why is no real title available?)
• A characterization of perfect graphs
• A note on superbrittle graphs
• Graph theory
• Optimizing weakly triangulated graphs
• Satgraphs and independent domination. I
• Split-Perfect Graphs: Characterizations and Algorithmic Use
• The strong perfect graph theorem
• Weakly triangulated graphs

Cited in

(9)

• On perfectness of sums of graphs
• scientific article; zbMATH DE number 4150226 (Why is no real title available?)
• A new characterization of perfect graphs
• Induced regular perfect graphs
• A Sum of Squares Characterization of Perfect Graphs
• A new characterization of trivially perfect graphs
• A characterization of star-perfect graphs
• Graphs omitting sums of complete graphs
• Minimal imperfect graphs: A simple approach

This page was built for publication: Sum-perfect graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1735702)