<p>A function <InlineEquation ID="IEq7"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="373_2025_2897_Article_IEq7.gif" Format="GIF" Height="17" Rendition="HTML" Resolution="72" Type="Linedraw" Width="76" /> </InlineMediaObject> <EquationSource Format="TEX">$f:{\mathbb {N}} \rightarrow {\mathbb {R}}$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>f</mi> <mo>:</mo> <mi mathvariant="double-struck">N</mi> <mo stretchy="false">→</mo> <mi mathvariant="double-struck">R</mi> </mrow> </math></EquationSource> </InlineEquation> is called a <InlineEquation ID="IEq8"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="373_2025_2897_Article_IEq8.gif" Format="GIF" Height="12" Rendition="HTML" Resolution="72" Type="Linedraw" Width="15" /> </InlineMediaObject> <EquationSource Format="TEX">$\chi $</EquationSource> <EquationSource Format="MATHML"><math> <mi>χ</mi> </math></EquationSource> </InlineEquation>-binding function for a hereditary family <InlineEquation ID="IEq9"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="373_2025_2897_Article_IEq9.gif" Format="GIF" Height="14" Rendition="HTML" Resolution="72" Type="Linedraw" Width="21" /> </InlineMediaObject> <EquationSource Format="TEX">${\mathscr {G}}$</EquationSource> <EquationSource Format="MATHML"><math> <mi mathvariant="script">G</mi> </math></EquationSource> </InlineEquation> of graphs, if <InlineEquation ID="IEq10"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="373_2025_2897_Article_IEq10.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="121" /> </InlineMediaObject> <EquationSource Format="TEX">$\chi (G) \le f(\omega (G))$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>χ</mi> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> <mo>≤</mo> <mi>f</mi> <mo stretchy="false">(</mo> <mi>ω</mi> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> for every <InlineEquation ID="IEq11"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="373_2025_2897_Article_IEq11.gif" Format="GIF" Height="15" Rendition="HTML" Resolution="72" Type="Linedraw" Width="55" /> </InlineMediaObject> <EquationSource Format="TEX">$G \in {\mathscr {G}}$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>G</mi> <mo>∈</mo> <mi mathvariant="script">G</mi> </mrow> </math></EquationSource> </InlineEquation> where <InlineEquation ID="IEq12"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="373_2025_2897_Article_IEq12.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="39" /> </InlineMediaObject> <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> and <InlineEquation ID="IEq13"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="373_2025_2897_Article_IEq13.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="38" /> </InlineMediaObject> <EquationSource Format="TEX">$\omega (G)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>ω</mi> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> denote the chromatic number and clique number respectively. In his influential work, Gyaŕfaś (1987) showed that the family of (<InlineEquation ID="IEq14"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="373_2025_2897_Article_IEq14.gif" Format="GIF" Height="16" Rendition="HTML" Resolution="72" Type="Linedraw" Width="70" /> </InlineMediaObject> <EquationSource Format="TEX">$2K_1 \cup K_2$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mn>2</mn> <msub> <mi>K</mi> <mn>1</mn> </msub> <mo>∪</mo> <msub> <mi>K</mi> <mn>2</mn> </msub> </mrow> </math></EquationSource> </InlineEquation>)-free graphs and the family of (<InlineEquation ID="IEq15"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="373_2025_2897_Article_IEq15.gif" Format="GIF" Height="16" Rendition="HTML" Resolution="72" Type="Linedraw" Width="58" /> </InlineMediaObject> <EquationSource Format="TEX">$P_3 \cup K_1$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi>P</mi> <mn>3</mn> </msub> <mo>∪</mo> <msub> <mi>K</mi> <mn>1</mn> </msub> </mrow> </math></EquationSource> </InlineEquation>)-free graphs are <InlineEquation ID="IEq16"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="373_2025_2897_Article_IEq16.gif" Format="GIF" Height="12" Rendition="HTML" Resolution="72" Type="Linedraw" Width="15" /> </InlineMediaObject> <EquationSource Format="TEX">$\chi $</EquationSource> <EquationSource Format="MATHML"><math> <mi>χ</mi> </math></EquationSource> </InlineEquation>-bounded. Randerath and Schiermeyer (2004) improved the <InlineEquation ID="IEq17"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="373_2025_2897_Article_IEq17.gif" Format="GIF" Height="12" Rendition="HTML" Resolution="72" Type="Linedraw" Width="15" /> </InlineMediaObject> <EquationSource Format="TEX">$\chi $</EquationSource> <EquationSource Format="MATHML"><math> <mi>χ</mi> </math></EquationSource> </InlineEquation>-binding functions of both these classes to <InlineEquation ID="IEq18"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="373_2025_2897_Article_IEq18.gif" Format="GIF" Height="43" Rendition="HTML" Resolution="72" Type="Linedraw" Width="75" /> </InlineMediaObject> <EquationSource Format="TEX">$\left( {\begin{array}{c}x + 1\\ 2\end{array}}\right) $</EquationSource> <EquationSource Format="MATHML"><math> <mfenced close=")" open="("> <mrow> <mtable> <mtr> <mtd> <mrow> <mi>x</mi> <mo>+</mo> <mn>1</mn> </mrow> </mtd> </mtr> <mtr> <mtd> <mrow> <mrow /> <mn>2</mn> </mrow> </mtd> </mtr> </mtable> </mrow> </mfenced> </math></EquationSource> </InlineEquation>. In this paper, we further improve the <InlineEquation ID="IEq19"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="373_2025_2897_Article_IEq19.gif" Format="GIF" Height="12" Rendition="HTML" Resolution="72" Type="Linedraw" Width="15" /> </InlineMediaObject> <EquationSource Format="TEX">$\chi $</EquationSource> <EquationSource Format="MATHML"><math> <mi>χ</mi> </math></EquationSource> </InlineEquation>-binding function of both these classes to <InlineEquation ID="IEq20"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="373_2025_2897_Article_IEq20.gif" Format="GIF" Height="25" Rendition="HTML" Resolution="72" Type="Linedraw" Width="14" /> </InlineMediaObject> <EquationSource Format="TEX">$\frac{x^2}{2}$</EquationSource> <EquationSource Format="MATHML"><math> <mfrac> <msup> <mi>x</mi> <mn>2</mn> </msup> <mn>2</mn> </mfrac> </math></EquationSource> </InlineEquation> for <InlineEquation ID="IEq21"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="373_2025_2897_Article_IEq21.gif" Format="GIF" Height="15" Rendition="HTML" Resolution="72" Type="Linedraw" Width="42" /> </InlineMediaObject> <EquationSource Format="TEX">$x \ge 3$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>x</mi> <mo>≥</mo> <mn>3</mn> </mrow> </math></EquationSource> </InlineEquation>. Furthermore, we obtain a tight chromatic bound for (<InlineEquation ID="IEq22"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="373_2025_2897_Article_IEq22.gif" Format="GIF" Height="16" Rendition="HTML" Resolution="72" Type="Linedraw" Width="58" /> </InlineMediaObject> <EquationSource Format="TEX">$P_3 \cup K_1$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi>P</mi> <mn>3</mn> </msub> <mo>∪</mo> <msub> <mi>K</mi> <mn>1</mn> </msub> </mrow> </math></EquationSource> </InlineEquation>)-free graphs with clique number 4.</p>

Towards Optimal $\chi $-Binding Functions of ($2K_1 \cup K_2$)-Free Graphs and ($P_3 \cup K_1$)-Free Graphs

期刊论文
发表日期：

2025年2月22日

查看全文

C. U. Angeliya,
Sheshayya Choudum,
Mayamma Joseph

摘要

A function $f:{\mathbb {N}} \rightarrow {\mathbb {R}}$ $f : N \to R$ is called a $\chi $ $χ$ -binding function for a hereditary family ${\mathscr {G}}$ $G$ of graphs, if $\chi (G) \le f(\omega (G))$ $χ (G) \leq f (ω (G))$ for every $G \in {\mathscr {G}}$ $G \in G$ where $\chi (G)$ $χ (G)$ and $\omega (G)$ $ω (G)$ denote the chromatic number and clique number respectively. In his influential work, Gyaŕfaś (1987) showed that the family of ( $2K_1 \cup K_2$ $2 K_{1} \cup K_{2}$ )-free graphs and the family of ( $P_3 \cup K_1$ $P_{3} \cup K_{1}$ )-free graphs are $\chi $ $χ$ -bounded. Randerath and Schiermeyer (2004) improved the $\chi $ $χ$ -binding functions of both these classes to $\left( {\begin{array}{c}x + 1\\ 2\end{array}}\right) $ $(\begin{matrix} x + 1 \\ 2 \end{matrix})$ . In this paper, we further improve the $\chi $ $χ$ -binding function of both these classes to $\frac{x^2}{2}$ $\frac{x^{2}}{2}$ for $x \ge 3$ $x \geq 3$ . Furthermore, we obtain a tight chromatic bound for ( $P_3 \cup K_1$ $P_{3} \cup K_{1}$ )-free graphs with clique number 4.

Towards Optimal \(\chi \)-Binding Functions of (\(2K_1 \cup K_2\))-Free Graphs and (\(P_3 \cup K_1\))-Free Graphs

摘要