Coloring of some $(P_2\cup P_4)$-free graphs
Fuente:
arXiv
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866917873787600896 |
|---|---|
| author | Ran, Chen xiaowen, Zhang |
| author_facet | Ran, Chen xiaowen, Zhang |
| contents | 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 $χ(G)\le 3ω(G)-2$ if $G$ is a ($P_2\cup P_4$, gem)-free graph, $χ(G)\le \frac{ω(G)^2+3ω(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$, $χ(G)\leq4$ if $ω(G)=2$, $χ(G)\leq7$ if $ω(G)=3$, $χ(G)\leq9$ if $ω(G)=4$, and $χ(G)\leq2ω(G)-1$ if $ω(G)\ge 5$. Moreover, we prove that $G$ is perfect if $G$ is ($P_2\cup P_4$, diamond, $C_5$)-free with $ω(G)\geq5$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2412_14524 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Coloring of some $(P_2\cup P_4)$-free graphs Ran, Chen xiaowen, Zhang Combinatorics 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 $χ(G)\le 3ω(G)-2$ if $G$ is a ($P_2\cup P_4$, gem)-free graph, $χ(G)\le \frac{ω(G)^2+3ω(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$, $χ(G)\leq4$ if $ω(G)=2$, $χ(G)\leq7$ if $ω(G)=3$, $χ(G)\leq9$ if $ω(G)=4$, and $χ(G)\leq2ω(G)-1$ if $ω(G)\ge 5$. Moreover, we prove that $G$ is perfect if $G$ is ($P_2\cup P_4$, diamond, $C_5$)-free with $ω(G)\geq5$. |
| title | Coloring of some $(P_2\cup P_4)$-free graphs |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2412.14524 |