




















For a graph $G$ with the vertex set $V(G)$ and the edge set $E(G)$ and a star subgraph $S$ of $G$, let $α_S(G)$ be the maximum number of vertices in $G$ such that no two of them are in the same star subgraph $S$ and $θ_S(G)$ be the minimum number of star subgraph $S$ that cover the vertices of $G$. A graph $G$ is called $S$-perfect if for every induced subgraph $H$ of $G$, $α_S(H)=θ_S(H)$. Motivated by perfect graphs discovered by Berge, Ravindra introduced $S$-perfect graphs. In this paper we prove that a triangulated graph is $S$-perfect if and only if $G$ is odd sun-free. This result leads to a conjecture which if proved is a structural characterization of $S$-perfect graphs in terms of forbidden subgraphs.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。