<p>Let <InlineEquation ID="IEq1"> <EquationSource Format="MATHML"><math> <mi mathvariant="script">F</mi> </math></EquationSource> <EquationSource Format="TEX">$\mathcal{F}$</EquationSource> </InlineEquation> be a family of graphs. For a graph <i>G</i>, define <InlineEquation ID="IEq2"> <EquationSource Format="MATHML"><math> <msub> <mi>θ</mi> <mi>F</mi> </msub> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> </math></EquationSource> <EquationSource Format="TEX">$\theta _{F}(G)$</EquationSource> </InlineEquation> as the minimum number of induced subgraphs of <i>G</i>, each isomorphic to a member of <InlineEquation ID="IEq3"> <EquationSource Format="MATHML"><math> <mi mathvariant="script">F</mi> </math></EquationSource> <EquationSource Format="TEX">$\mathcal{F}$</EquationSource> </InlineEquation>, needed to cover <InlineEquation ID="IEq4"> <EquationSource Format="MATHML"><math> <mi>V</mi> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> </math></EquationSource> <EquationSource Format="TEX">$V(G)$</EquationSource> </InlineEquation>, and <InlineEquation ID="IEq5"> <EquationSource Format="MATHML"><math> <msub> <mi>α</mi> <mi>F</mi> </msub> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> </math></EquationSource> <EquationSource Format="TEX">$\alpha _{F}(G)$</EquationSource> </InlineEquation> as the maximum number of vertices in <i>G</i> such that no two are contained in an induced subgraph of <i>G</i> isomorphic to a member of <InlineEquation ID="IEq6"> <EquationSource Format="MATHML"><math> <mi mathvariant="script">F</mi> </math></EquationSource> <EquationSource Format="TEX">$\mathcal{F}$</EquationSource> </InlineEquation>. In this paper, we focus on the fundamental inequality of graphs, <InlineEquation ID="IEq7"> <EquationSource Format="MATHML"><math> <msub> <mi>θ</mi> <mi>F</mi> </msub> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> <mo>≥</mo> <msub> <mi>α</mi> <mi>F</mi> </msub> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> </math></EquationSource> <EquationSource Format="TEX">$\theta _{F}(G) \geq \alpha _{F}(G)$</EquationSource> </InlineEquation>, and the characterization of <InlineEquation ID="IEq8"> <EquationSource Format="MATHML"><math> <mi mathvariant="script">F</mi> </math></EquationSource> <EquationSource Format="TEX">$\mathcal{F}$</EquationSource> </InlineEquation>-perfect graphs, where equality holds for all induced subgraphs. Specifically, we investigate induced star-perfect graphs, where <InlineEquation ID="IEq9"> <EquationSource Format="MATHML"><math> <mi mathvariant="script">F</mi> </math></EquationSource> <EquationSource Format="TEX">$\mathcal{F}$</EquationSource> </InlineEquation> is the family of stars and <InlineEquation ID="IEq10"> <EquationSource Format="MATHML"><math> <msub> <mi>ω</mi> <mi>F</mi> </msub> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> </math></EquationSource> <EquationSource Format="TEX">$\omega _{F}(G)$</EquationSource> </InlineEquation> is the size of a maximum induced star in <i>G</i>. 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 <InlineEquation ID="IEq11"> <EquationSource Format="MATHML"><math> <msub> <mi>α</mi> <mi>F</mi> </msub> <mo stretchy="false">(</mo> <mi>H</mi> <mo stretchy="false">)</mo> <msub> <mi>ω</mi> <mi>F</mi> </msub> <mo stretchy="false">(</mo> <mi>H</mi> <mo stretchy="false">)</mo> <mo>≥</mo> <mo stretchy="false">|</mo> <mi>V</mi> <mo stretchy="false">(</mo> <mi>H</mi> <mo stretchy="false">)</mo> <mo stretchy="false">|</mo> </math></EquationSource> <EquationSource Format="TEX">$\alpha _{F}(H) \omega _{F}(H) \geq |V(H)|$</EquationSource> </InlineEquation> holds for every induced subgraph <i>H</i> of an induced star-perfect graph.</p>

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

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

  • James Alex,
  • Louis Caccetta

摘要

Let F $\mathcal{F}$ be a family of graphs. For a graph G, define θ F ( G ) $\theta _{F}(G)$ as the minimum number of induced subgraphs of G, each isomorphic to a member of F $\mathcal{F}$ , needed to cover V ( G ) $V(G)$ , and α F ( G ) $\alpha _{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 $\mathcal{F}$ . In this paper, we focus on the fundamental inequality of graphs, θ F ( G ) α F ( G ) $\theta _{F}(G) \geq \alpha _{F}(G)$ , and the characterization of F $\mathcal{F}$ -perfect graphs, where equality holds for all induced subgraphs. Specifically, we investigate induced star-perfect graphs, where F $\mathcal{F}$ is the family of stars and ω F ( G ) $\omega _{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 ) | $\alpha _{F}(H) \omega _{F}(H) \geq |V(H)|$ holds for every induced subgraph H of an induced star-perfect graph.