Answers are grounded in this paper and cite their sources.
Proves Lovász's inequality for induced star-perfect graphs, indicating new insights into graph theory.
Let F F be a family of graphs. For a graph G , define θ F(G) θ F ( G ) as the minimum number of induced subgraphs of G , each isomorphic to a member of F F , needed to cover $V(G)$ V ( G ) , and α F(G) α F ( G ) as the maximum number of vertices in G such that no two are contained in an induced subgraph of G isomorphic to a member of F F . In this paper, we focus on the fundamental inequality of graphs, θ F(G) ≥ α F(G) θ F ( G ) ≥ α F ( G ) , and the characterization of F F -perfect graphs, where equality holds for all induced subgraphs. Specifically, we investigate induced star-perfect graphs, where F F is the family of stars and ω F(G) ω F ( G ) is the size of a maximum induced star in G . The characterization of induced star-perfect graphs by a set of forbidden induced subgraphs was conjectured by Ravindra in 2011 and was proved in 2024. Here, we present a shorter proof of this characterization, applying our main result that the inequality α F(H) ω F(H) ≥ |V(H)| α F ( H ) ω F ( H ) ≥ | V ( H ) | holds for every induced subgraph H of an induced star-perfect graph.
No takes yet. Share an insight, caveat, or question.
Alex et al. (2026) studied this question.
Synapse has enriched 10 related papers. Consider them for comparative context: