Sum-perfect graphs

DOI10.1016/J.DAM.2018.12.015zbMATH Open1407.05098arXiv1710.07546OpenAlexW2765711561MaRDI QIDQ1735702FDOQ1735702

Authors: Bart Litjens, Vaidy Sivaraman, Sven C. Polak 

Publication date: 28 March 2019

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

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.

Full work available at URL: https://arxiv.org/abs/1710.07546

Recommendations

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

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)

Cites Work

• Graph theory
• A characterization of perfect graphs
• The strong perfect graph theorem
• Weakly triangulated graphs
• Title not available (Why is that?)
• A note on superbrittle graphs
• Optimizing weakly triangulated graphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• Split-Perfect Graphs: Characterizations and Algorithmic Use
• Satgraphs and independent domination. I

Cited In (9)

• On perfectness of sums of graphs
• Title not available (Why is that?)
• Induced regular perfect graphs
• A new characterization of 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)