On the validity of Lovász’s inequality for induced star-perfect graphs

Abstract Let $\mathcal{F}$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>F</mml:mi> </mml:math> be a family of graphs. For a graph G , define $\theta _{F}(G)$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msub> <mml:mi>θ</mml:mi> <mml:mi>F</mml:mi> </mml:msub> <mml:mo>(</mml:mo> <mml:mi>G</mml:mi> <mml:mo>)</mml:mo> </mml:math> as the minimum number of induced subgraphs of G , each isomorphic to a member of $\mathcal{F}$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>F</mml:mi> </mml:math> , needed to cover $V(G)$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>V</mml:mi> <mml:mo>(</mml:mo> <mml:mi>G</mml:mi> <mml:mo>)</mml:mo> </mml:math> , and $\alpha _{F}(G)$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msub> <mml:mi>α</mml:mi> <mml:mi>F</mml:mi> </mml:msub> <mml:mo>(</mml:mo> <mml:mi>G</mml:mi> <mml:mo>)</mml:mo> </mml:math> 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 $\mathcal{F}$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>F</mml:mi> </mml:math> . In this paper, we focus on the fundamental inequality of graphs, $\theta _{F}(G) \geq \alpha _{F}(G)$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msub> <mml:mi>θ</mml:mi> <mml:mi>F</mml:mi> </mml:msub> <mml:mo>(</mml:mo> <mml:mi>G</mml:mi> <mml:mo>)</mml:mo> <mml:mo>≥</mml:mo> <mml:msub> <mml:mi>α</mml:mi> <mml:mi>F</mml:mi> </mml:msub> <mml:mo>(</mml:mo> <mml:mi>G</mml:mi> <mml:mo>)</mml:mo> </mml:math> , and the characterization of $\mathcal{F}$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>F</mml:mi> </mml:math> -perfect graphs, where equality holds for all induced subgraphs. Specifically, we investigate induced star-perfect graphs, where $\mathcal{F}$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>F</mml:mi> </mml:math> is the family of stars and $\omega _{F}(G)$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msub> <mml:mi>ω</mml:mi> <mml:mi>F</mml:mi> </mml:msub> <mml:mo>(</mml:mo> <mml:mi>G</mml:mi> <mml:mo>)</mml:mo> </mml:math> 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 $\alpha _{F}(H) \omega _{F}(H) \geq |V(H)|$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msub> <mml:mi>α</mml:mi> <mml:mi>F</mml:mi> </mml:msub> <mml:mo>(</mml:mo> <mml:mi>H</mml:mi> <mml:mo>)</mml:mo> <mml:msub> <mml:mi>ω</mml:mi> <mml:mi>F</mml:mi> </mml:msub> <mml:mo>(</mml:mo> <mml:mi>H</mml:mi> <mml:mo>)</mml:mo> <mml:mo>≥</mml:mo> <mml:mo>|</mml:mo> <mml:mi>V</mml:mi> <mml:mo>(</mml:mo> <mml:mi>H</mml:mi> <mml:mo>)</mml:mo> <mml:mo>|</mml:mo> </mml:math> holds for every induced subgraph H of an induced star-perfect graph.