An optimal chromatic bound for ($P_2+P_3$, gem)-free graphs

Abstract

Given a graph $G$, the parameters $\ddot{I}‡(G)$ and $\ddot{I}‰(G)$ respectively denote the chromatic number and the clique number of $G$. A function $f:\mathbb{N}\to \mathbb{N}$ such that $f(1)=1$ and $f(x)\ge x$, for all $x\in \mathbb{N}$ is called a $\ddot{I}‡$-binding function for the given class of graphs $\mathcal{G}$ if every $G\in \mathcal{G}$ satisfies $\ddot{I}‡(G)\le f(\ddot{I}‰(G))$, and the \emph{smallest $\ddot{I}‡$-binding function} $f^{\ast }$ for $\mathcal{G}$ is defined as $f^*(x) := \max\{χ(G)\mid G\in {\cal G} \mbox{ and } ω(G)=x\}$. In general, the problem of obtaining the smallest $\ddot{I}‡$-binding function for the given class of graphs seems to be extremely hard, and only a few classes of graphs are studied in this direction. In this paper, we study the class of ($P_2+P_3$, gem)-free graphs, and prove that the function $\ddot{I}•:\mathbb{N}\to \mathbb{N}$ defined by $\ddot{I}•(1)=1$, $\ddot{I}•(2)=4$, $\ddot{I}•(3)=6$ and $\ddot{I}•(x)=\lceil \frac{1}{4}(5x-1)\rceil$, for $x\ge 4$ is the smallest $\ddot{I}‡$-binding function for the class of ($P_2+P_3$, gem)-free graphs.