REVIEW 1 cited by
An optimal chromatic bound for ($P_2+P_3$, gem)-free graphs
Not yet reviewed by Pith; the record is open.
This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.
SPECIMEN: schema-true, not a live event
T0 review · schema-true
One-sentence machine reading of the paper's core claim.
pith:XXXXXXXX · record.json · timestamp
abstract
Given a graph $G$, the parameters $\chi(G)$ and $\omega(G)$ respectively denote the chromatic number and the clique number of $G$. A function $f : \mathbb{N} \rightarrow \mathbb{N}$ such that $f(1) = 1$ and $f(x) \geq x$, for all $x \in \mathbb{N}$ is called a $\chi$-binding function for the given class of graphs $\cal{G}$ if every $G \in \cal{G}$ satisfies $\chi(G) \leq f(\omega(G))$, and the \emph{smallest $\chi$-binding function} $f^*$ for $\cal{G}$ is defined as $f^*(x) := \max\{\chi(G)\mid G\in {\cal G} \mbox{ and } \omega(G)=x\}$. In general, the problem of obtaining the smallest $\chi$-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 $\phi:\mathbb{N}\rightarrow \mathbb{N}$ defined by $\phi(1)=1$, $\phi(2)=4$, $\phi(3)=6$ and $\phi(x)=\left\lceil\frac{1}{4}(5x-1)\right\rceil$, for $x\geq 4$ is the smallest $\chi$-binding function for the class of ($P_2+ P_3$, gem)-free graphs.
Forward citations
Cited by 1 Pith paper
-
Coloring of some $(P_2\cup P_4)$-free graphs
For (P2∪P4, gem)-free, (P2∪P4, butterfly)-free, and (P2∪P4, diamond)-free graphs, the paper establishes explicit χ-binding functions, and shows (P2∪P4, diamond, C5)-free graphs with clique number at least 5 are perfect.
Discussion (0). Continue with ORCID to comment.