For two vertex-disjoint graphs H and F, let <InlineEquation ID="IEq4"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="373_2025_2974_Article_IEq4.gif" Format="GIF" Height="14" Rendition="HTML" Resolution="72" Type="Linedraw" Width="50" /> </InlineMediaObject> <EquationSource Format="TEX">$H \cup F$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>H</mi> <mo>∪</mo> <mi>F</mi> </mrow> </math></EquationSource> </InlineEquation> denote their disjoint union and <InlineEquation ID="IEq5"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="373_2025_2974_Article_IEq5.gif" Format="GIF" Height="15" Rendition="HTML" Resolution="72" Type="Linedraw" Width="51" /> </InlineMediaObject> <EquationSource Format="TEX">$H + F$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>H</mi> <mo>+</mo> <mi>F</mi> </mrow> </math></EquationSource> </InlineEquation> their join. A <InlineEquation ID="IEq6"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="373_2025_2974_Article_IEq6.gif" Format="GIF" Height="16" Rendition="HTML" Resolution="72" Type="Linedraw" Width="23" /> </InlineMediaObject> <EquationSource Format="TEX">$W_4$</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>W</mi> <mn>4</mn> </msub> </math></EquationSource> </InlineEquation> is defined as <InlineEquation ID="IEq7"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="373_2025_2974_Article_IEq7.gif" Format="GIF" Height="16" Rendition="HTML" Resolution="72" Type="Linedraw" Width="60" /> </InlineMediaObject> <EquationSource Format="TEX">$K_1 + C_4$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi>K</mi> <mn>1</mn> </msub> <mo>+</mo> <msub> <mi>C</mi> <mn>4</mn> </msub> </mrow> </math></EquationSource> </InlineEquation>. In this paper, we establish improved bounds on the chromatic number of <InlineEquation ID="IEq8"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="373_2025_2974_Article_IEq8.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="97" /> </InlineMediaObject> <EquationSource Format="TEX">$(P_3 \cup P_2, W_4)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mo stretchy="false">(</mo> <msub> <mi>P</mi> <mn>3</mn> </msub> <mo>∪</mo> <msub> <mi>P</mi> <mn>2</mn> </msub> <mo>,</mo> <msub> <mi>W</mi> <mn>4</mn> </msub> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation>-free graphs. We prove that for any such graph G, <InlineEquation ID="IEq9"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="373_2025_2974_Article_IEq9.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="106" /> </InlineMediaObject> <EquationSource Format="TEX">$\chi (G) \le 2\omega (G)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>χ</mi> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> <mo>≤</mo> <mn>2</mn> <mi>ω</mi> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation>, which reduces the previous bound of <InlineEquation ID="IEq10"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="373_2025_2974_Article_IEq10.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="46" /> </InlineMediaObject> <EquationSource Format="TEX">$3\omega (G)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mn>3</mn> <mi>ω</mi> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> due to Wang and Zhang [2022]. This bound is shown to be tight for clique numbers <InlineEquation ID="IEq11"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="373_2025_2974_Article_IEq11.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="103" /> </InlineMediaObject> <EquationSource Format="TEX">$\omega (G) \in \{2,3\}$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>ω</mi> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> <mo>∈</mo> <mo stretchy="false">{</mo> <mn>2</mn> <mo>,</mo> <mn>3</mn> <mo stretchy="false">}</mo> </mrow> </math></EquationSource> </InlineEquation>, as demonstrated by the Grőstzsch graph (<InlineEquation ID="IEq12"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="373_2025_2974_Article_IEq12.gif" Format="GIF" Height="16" Rendition="HTML" Resolution="72" Type="Linedraw" Width="91" /> </InlineMediaObject> <EquationSource Format="TEX">$\omega =2, \chi =4$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>ω</mi> <mo>=</mo> <mn>2</mn> <mo>,</mo> <mi>χ</mi> <mo>=</mo> <mn>4</mn> </mrow> </math></EquationSource> </InlineEquation>) and the complement of the Schla̋fli graph (<InlineEquation ID="IEq13"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="373_2025_2974_Article_IEq13.gif" Format="GIF" Height="16" Rendition="HTML" Resolution="72" Type="Linedraw" Width="91" /> </InlineMediaObject> <EquationSource Format="TEX">$\omega =3, \chi =6$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>ω</mi> <mo>=</mo> <mn>3</mn> <mo>,</mo> <mi>χ</mi> <mo>=</mo> <mn>6</mn> </mrow> </math></EquationSource> </InlineEquation>). Our result also generalizes several known bounds for subclasses of <InlineEquation ID="IEq14"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="373_2025_2974_Article_IEq14.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="67" /> </InlineMediaObject> <EquationSource Format="TEX">$(P_3 \cup P_2)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mo stretchy="false">(</mo> <msub> <mi>P</mi> <mn>3</mn> </msub> <mo>∪</mo> <msub> <mi>P</mi> <mn>2</mn> </msub> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation>-free graphs.

Improved bounds on the chromatic number of ($P_3\cup P_2, W_4$)-free graphs

期刊论文
发表日期：

2025年9月25日

查看全文

Di Wu,
Jinfeng Li,
Rui Li

摘要

For two vertex-disjoint graphs H and F, let $H \cup F$ $H \cup F$ denote their disjoint union and $H + F$ $H + F$ their join. A $W_4$ $W_{4}$ is defined as $K_1 + C_4$ $K_{1} + C_{4}$ . In this paper, we establish improved bounds on the chromatic number of $(P_3 \cup P_2, W_4)$ $(P_{3} \cup P_{2}, W_{4})$ -free graphs. We prove that for any such graph G, $\chi (G) \le 2\omega (G)$ $χ (G) \leq 2 ω (G)$ , which reduces the previous bound of $3\omega (G)$ $3 ω (G)$ due to Wang and Zhang [2022]. This bound is shown to be tight for clique numbers $\omega (G) \in \{2,3\}$ $ω (G) \in {2, 3}$ , as demonstrated by the Grőstzsch graph ( $\omega =2, \chi =4$ $ω = 2, χ = 4$ ) and the complement of the Schla̋fli graph ( $\omega =3, \chi =6$ $ω = 3, χ = 6$ ). Our result also generalizes several known bounds for subclasses of $(P_3 \cup P_2)$ $(P_{3} \cup P_{2})$ -free graphs.

Improved bounds on the chromatic number of (\(P_3\cup P_2, W_4\))-free graphs

摘要