Scholarlink

<p>A <i>gem</i> is a graph that consists of an induced path on 4-vertices plus a vertex which is adjacent to all the vertices of that path. The Lescure-Meyniel conjecture is the analogue of Hadwiger’s conjecture for the immersion order. It states that for every graph <i>G</i>, there exists a complete graph <InlineEquation ID="IEq1"> <EquationSource Format="TEX">\(K_{\chi (G)}\)</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>K</mi> <mrow> <mi>χ</mi> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> </mrow> </msub> </math></EquationSource> </InlineEquation> that is an immersion in <i>G</i>. Similar to Hadwiger’s conjecture, the Lescure-Meyniel conjecture remains an open problem even for graphs with an independence number of 2. We show that for every graph <i>G</i> with independence number <InlineEquation ID="IEq2"> <EquationSource Format="TEX">\(\alpha (G)\le 2\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>α</mi> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> <mo>≤</mo> <mn>2</mn> </mrow> </math></EquationSource> </InlineEquation>, if <i>G</i> is <i>gem</i>-free, then <i>G</i> satisfies the Lescure-Meyniel conjecture.</p>

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

Lescure-Meyniel conjecture holds for Gem-free graphs with independence number two

  • 期刊论文

  • 发表日期：

    2026年2月16日

查看全文
  • Zijian Deng,
  • Caibing Chang,
  • Yan Liu

摘要

A gem is a graph that consists of an induced path on 4-vertices plus a vertex which is adjacent to all the vertices of that path. The Lescure-Meyniel conjecture is the analogue of Hadwiger’s conjecture for the immersion order. It states that for every graph G, there exists a complete graph \(K_{\chi (G)}\) K χ ( G ) that is an immersion in G. Similar to Hadwiger’s conjecture, the Lescure-Meyniel conjecture remains an open problem even for graphs with an independence number of 2. We show that for every graph G with independence number \(\alpha (G)\le 2\) α ( G ) ≤ 2 , if G is gem-free, then G satisfies the Lescure-Meyniel conjecture.