Let F and H be two vertex disjoint graphs. The union <InlineEquation ID="IEq3"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="373_2025_2894_Article_IEq3.gif" Format="GIF" Height="14" Rendition="HTML" Resolution="72" Type="Linedraw" Width="51" /> </InlineMediaObject> <EquationSource Format="TEX">$F\cup H$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>F</mi> <mo>∪</mo> <mi>H</mi> </mrow> </math></EquationSource> </InlineEquation> is the graph with <InlineEquation ID="IEq4"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="373_2025_2894_Article_IEq4.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="196" /> </InlineMediaObject> <EquationSource Format="TEX">$V(F\cup H)=V(F)\cup V(H)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>V</mi> <mo stretchy="false">(</mo> <mi>F</mi> <mo>∪</mo> <mi>H</mi> <mo stretchy="false">)</mo> <mo>=</mo> <mi>V</mi> <mo stretchy="false">(</mo> <mi>F</mi> <mo stretchy="false">)</mo> <mo>∪</mo> <mi>V</mi> <mo stretchy="false">(</mo> <mi>H</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> and <InlineEquation ID="IEq5"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="373_2025_2894_Article_IEq5.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="196" /> </InlineMediaObject> <EquationSource Format="TEX">$E(F\cup H)=E(F)\cup E(H)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>E</mi> <mo stretchy="false">(</mo> <mi>F</mi> <mo>∪</mo> <mi>H</mi> <mo stretchy="false">)</mo> <mo>=</mo> <mi>E</mi> <mo stretchy="false">(</mo> <mi>F</mi> <mo stretchy="false">)</mo> <mo>∪</mo> <mi>E</mi> <mo stretchy="false">(</mo> <mi>H</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation>. We use <InlineEquation ID="IEq6"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="373_2025_2894_Article_IEq6.gif" Format="GIF" Height="16" Rendition="HTML" Resolution="72" Type="Linedraw" Width="21" /> </InlineMediaObject> <EquationSource Format="TEX">$P_k$</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>P</mi> <mi>k</mi> </msub> </math></EquationSource> </InlineEquation> to denote a path on k vertices and use house to denote the complement of <InlineEquation ID="IEq7"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="373_2025_2894_Article_IEq7.gif" Format="GIF" Height="16" Rendition="HTML" Resolution="72" Type="Linedraw" Width="18" /> </InlineMediaObject> <EquationSource Format="TEX">$P_5$</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>P</mi> <mn>5</mn> </msub> </math></EquationSource> </InlineEquation>. In this paper, we show that if G is a (<InlineEquation ID="IEq8"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="373_2025_2894_Article_IEq1.gif" Format="GIF" Height="16" Rendition="HTML" Resolution="72" Type="Linedraw" Width="55" /> </InlineMediaObject> <EquationSource Format="TEX">$P_3\cup P_2$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi>P</mi> <mn>3</mn> </msub> <mo>∪</mo> <msub> <mi>P</mi> <mn>2</mn> </msub> </mrow> </math></EquationSource> </InlineEquation>, house)-free graph, then <InlineEquation ID="IEq9"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="373_2025_2894_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>. Moreover, this bound is optimal when <InlineEquation ID="IEq10"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="373_2025_2894_Article_IEq10.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="69" /> </InlineMediaObject> <EquationSource Format="TEX">$\omega (G)\ge 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>.

Optimal Chromatic Bound for ($P_3\cup P_2$, House)-Free Graphs

期刊论文
发表日期：

2025年1月22日

查看全文

Rui Li,
Jinfeng Li,
Di Wu

摘要

Let F and H be two vertex disjoint graphs. The union $F\cup H$ $F \cup H$ is the graph with $V(F\cup H)=V(F)\cup V(H)$ $V (F \cup H) = V (F) \cup V (H)$ and $E(F\cup H)=E(F)\cup E(H)$ $E (F \cup H) = E (F) \cup E (H)$ . We use $P_k$ $P_{k}$ to denote a path on k vertices and use house to denote the complement of $P_5$ $P_{5}$ . In this paper, we show that if G is a ( $P_3\cup P_2$ $P_{3} \cup P_{2}$ , house)-free graph, then $\chi (G)\le 2\omega (G)$ $χ (G) \leq 2 ω (G)$ . Moreover, this bound is optimal when $\omega (G)\ge 2$ $ω (G) \geq 2$ .

Optimal Chromatic Bound for (\(P_3\cup P_2\), House)-Free Graphs

摘要