The reviewed record of science sign in
Pith

arxiv: 2412.14524 · v1 · pith:J5U2L23J · submitted 2024-12-19 · math.CO

Coloring of some (P₂cup P₄)-free graphs

Reviewed by Pith T0 review T1 audit T2 compute T3 formal T4 kernel pith:J5U2L23Jrecord.jsonopen to challenge →

classification math.CO
keywords omegagraphfreediamondgraphsrespverticesbutterfly
0
0 comments X
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$.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.