REVIEW
Coloring of some (P₂cup P₄)-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
Coloring of some (P₂cup P₄)-free graphs
read the original abstract
We denote a path on $t$ vertices as $P_t$ and a cycle on $t$ vertices as $C_t$. For two vertex-disjoint graphs $G_1$ and $G_2$, the {\em union} $G_1\cup G_2$ is the graph with $V(G_1\cup G_2)=V(G_1)\cup V(G_2)$ and $E(G_1\cup G_2)=E(G_1)\cup E(G_2)$. A {\em diamond} (resp. {\em gem}) is a graph consisting of a $P_3$ (resp. $P_4$) and a new vertex adjacent to all vertices of the $P_3$ (resp. $P_4$), and a {\em butterfly} is a graph consisting of two triangles that share one vertex. In this paper, we show that $\chi(G)\le 3\omega(G)-2$ if $G$ is a ($P_2\cup P_4$, gem)-free graph, $\chi(G)\le \frac{\omega(G)^2+3\omega(G)-2}{2}$ if $G$ is a ($P_2\cup P_4$, butterfly)-free graph. We also study the class of ($P_2\cup P_4$, diamond)-free graphs, and show that, for such a graph $G$, $\chi(G)\leq4$ if $\omega(G)=2$, $\chi(G)\leq7$ if $\omega(G)=3$, $\chi(G)\leq9$ if $\omega(G)=4$, and $\chi(G)\leq2\omega(G)-1$ if $\omega(G)\ge 5$. Moreover, we prove that $G$ is perfect if $G$ is ($P_2\cup P_4$, diamond, $C_5$)-free with $\omega(G)\geq5$.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.