Scholarlink

<p>Borodin and Kostochka conjectured that every graph <i>G</i> with Δ ≥ 9 satisfies <i>χ</i> ≤ max {<i>ω</i>, Δ − 1}. Gupta and Pradhan proved the Borodin-Kostochka conjecture for (<i>P</i><sub>5</sub>, <i>C</i><sub>4</sub>)-free graphs. In this paper, we prove the Borodin-Kostochka conjecture for (<i>P</i><sub>6</sub>, apple, torch)-free graphs, that is, graphs with no induced <i>P</i><sub>6</sub>, no induced <i>C</i><sub>5</sub> with a hanging edge, and no induced <i>C</i><sub>5</sub> and <i>C</i><sub>4</sub> sharing exactly an induced <i>P</i><sub>3</sub>. This generalizes the result of Gupta and Pradhan from the perspective of allowing the existence of <i>P</i><sub>5</sub>.</p>

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

Borodin-Kostochka Conjecture for a Family of P6-free Graphs

  • 期刊论文

  • 发表日期：

    2025年11月6日

查看全文
  • Di Wu,
  • Rong Wu

摘要

Borodin and Kostochka conjectured that every graph G with Δ ≥ 9 satisfies χ ≤ max {ω, Δ − 1}. Gupta and Pradhan proved the Borodin-Kostochka conjecture for (P5, C4)-free graphs. In this paper, we prove the Borodin-Kostochka conjecture for (P6, apple, torch)-free graphs, that is, graphs with no induced P6, no induced C5 with a hanging edge, and no induced C5 and C4 sharing exactly an induced P3. This generalizes the result of Gupta and Pradhan from the perspective of allowing the existence of P5.