A characterization of star-perfect graphs

Abstract

Motivated by Berge perfect graphs, we define star-perfect graphs and characterize them. For a finite simple graph G(V, E), let [Formula: see text] denote the minimum number of induced stars contained in G such that the union of their vertex sets is V(G), and let [Formula: see text] denote the maximum number of vertices in G such that no two of them are contained in the same induced star of G. We call a graph G star-perfect if [Formula: see text], for every induced subgraph H of G. A graph G is star-perfect if and only if G is [Formula: see text]-free, for every [Formula: see text]. A bipartite graph G is star-perfect if and only if every induced cycle in G is of length [Formula: see text]. The minimum parameter [Formula: see text] and the maximum parameter [Formula: see text] have been extensively studied in various contexts.

Keywords

• Perfect graph
• star-perfect graph
• star-imperfect graph
• 05C17
• 05C75