Let G be a graph, and let <InlineEquation ID="IEq4"> <EquationSource Format="TEX">$\Delta (G), \omega (G)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="normal">Δ</mi> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> <mo>,</mo> <mi>ω</mi> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation>, and <InlineEquation ID="IEq5"> <EquationSource Format="TEX">$\chi (G)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>χ</mi> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> represent the maximum degree, clique number, and chromatic number of G, respectively. Borodin and Kostochka conjectured that if G satisfies <InlineEquation ID="IEq6"> <EquationSource Format="TEX">$\Delta (G) \geqslant 9$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="normal">Δ</mi> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> <mo>⩾</mo> <mn>9</mn> </mrow> </math></EquationSource> </InlineEquation> and <InlineEquation ID="IEq7"> <EquationSource Format="TEX">$\omega (G) \leqslant \Delta (G) - 1$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>ω</mi> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> <mo>⩽</mo> <mi mathvariant="normal">Δ</mi> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> <mo>-</mo> <mn>1</mn> </mrow> </math></EquationSource> </InlineEquation>, then it follows that <InlineEquation ID="IEq8"> <EquationSource Format="TEX">$\chi (G) \leqslant \Delta (G) - 1$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>χ</mi> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> <mo>⩽</mo> <mi mathvariant="normal">Δ</mi> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> <mo>-</mo> <mn>1</mn> </mrow> </math></EquationSource> </InlineEquation>. Gupta and Pradhan proved that this conjecture is true for (<InlineEquation ID="IEq9"> <EquationSource Format="TEX">$P_5, C_4$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi>P</mi> <mn>5</mn> </msub> <mo>,</mo> <msub> <mi>C</mi> <mn>4</mn> </msub> </mrow> </math></EquationSource> </InlineEquation>)-free graphs (J. Appl. Math. Comp. 65, 877–884, 2021) and (<InlineEquation ID="IEq10"> <EquationSource Format="TEX">$P_6, C_4, H$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi>P</mi> <mn>6</mn> </msub> <mo>,</mo> <msub> <mi>C</mi> <mn>4</mn> </msub> <mo>,</mo> <mi>H</mi> </mrow> </math></EquationSource> </InlineEquation>)-free graphs, where H can be a bull or diamond (Discret. Appl. Math. 342, 334–346, 2024). In this paper, we expand upon their results and demonstrate that the conjecture is valid for (<InlineEquation ID="IEq11"> <EquationSource Format="TEX">$P_7, C_4, F$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi>P</mi> <mn>7</mn> </msub> <mo>,</mo> <msub> <mi>C</mi> <mn>4</mn> </msub> <mo>,</mo> <mi>F</mi> </mrow> </math></EquationSource> </InlineEquation>)-free graphs, where F is a bull or a kite.

Borodin–Kostochka Conjecture for some ($P_7,C_4$)-Free Graphs

期刊论文
发表日期：

2026年5月5日

查看全文

Ran Chen,
Di Wu,
Xiao-Wen Zhang

摘要

Let G be a graph, and let $\Delta (G), \omega (G)$ $Δ (G), ω (G)$ , and $\chi (G)$ $χ (G)$ represent the maximum degree, clique number, and chromatic number of G, respectively. Borodin and Kostochka conjectured that if G satisfies $\Delta (G) \geqslant 9$ $Δ (G) ⩾ 9$ and $\omega (G) \leqslant \Delta (G) - 1$ $ω (G) ⩽ Δ (G) - 1$ , then it follows that $\chi (G) \leqslant \Delta (G) - 1$ $χ (G) ⩽ Δ (G) - 1$ . Gupta and Pradhan proved that this conjecture is true for ( $P_5, C_4$ $P_{5}, C_{4}$ )-free graphs (J. Appl. Math. Comp. 65, 877–884, 2021) and ( $P_6, C_4, H$ $P_{6}, C_{4}, H$ )-free graphs, where H can be a bull or diamond (Discret. Appl. Math. 342, 334–346, 2024). In this paper, we expand upon their results and demonstrate that the conjecture is valid for ( $P_7, C_4, F$ $P_{7}, C_{4}, F$ )-free graphs, where F is a bull or a kite.

Borodin–Kostochka Conjecture for some (\(P_7,C_4\))-Free Graphs

摘要