Structure, Perfect Divisibility and Coloring of ($P_2\cup P_4, C_3$)-Free Graphs
Fuente:
arXiv
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866917357347143680 |
|---|---|
| author | Chen, Ran Wu, Di Zhang, Xiaowen |
| author_facet | Chen, Ran Wu, Di Zhang, Xiaowen |
| contents | Goedgebeur and Schaudt [J. Graph Theory 87 (2018) 188-207] conjectured that all 4-vertex-critical $(P_7,C_3)$-free graphs belongs to the family $\cal G$, which consists of seven explicitly defined graphs. In this paper, we establish a structural decomposition for $(P_2\cup P_4,C_3)$-free graphs and show that the conjecture holds for this class. Consequently, we determine the chromatic number of $(P_2\cup P_4, C_3)$-free graphs.
A graph $G$ is {\em perfectly divisible} if for each induced subgraph $H$ of $G$, $V(H)$ can be partitioned into $A$ and $B$ such that $H[A]$ is perfect and $ω(H[B])<ω(H)$. A {\em bull} is a graph consisting of a triangle with two disjoint pendant edges. Notice that the class of $(P_2\cup P_4, C_3)$-free graphs is a subclass of ($P_2\cup P_4$, bull)-free graphs. In this paper, we prove that a ($P_2\cup P_4$, bull)-free graph is perfectly divisible if and only if it contains no Mycielski-Grötzsch graph. This generalizes the main result of Deng and Chang [Graphs Combin. (2025) 41: 63]. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_14135 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Structure, Perfect Divisibility and Coloring of ($P_2\cup P_4, C_3$)-Free Graphs Chen, Ran Wu, Di Zhang, Xiaowen Combinatorics 05C15, 05C75 Goedgebeur and Schaudt [J. Graph Theory 87 (2018) 188-207] conjectured that all 4-vertex-critical $(P_7,C_3)$-free graphs belongs to the family $\cal G$, which consists of seven explicitly defined graphs. In this paper, we establish a structural decomposition for $(P_2\cup P_4,C_3)$-free graphs and show that the conjecture holds for this class. Consequently, we determine the chromatic number of $(P_2\cup P_4, C_3)$-free graphs. A graph $G$ is {\em perfectly divisible} if for each induced subgraph $H$ of $G$, $V(H)$ can be partitioned into $A$ and $B$ such that $H[A]$ is perfect and $ω(H[B])<ω(H)$. A {\em bull} is a graph consisting of a triangle with two disjoint pendant edges. Notice that the class of $(P_2\cup P_4, C_3)$-free graphs is a subclass of ($P_2\cup P_4$, bull)-free graphs. In this paper, we prove that a ($P_2\cup P_4$, bull)-free graph is perfectly divisible if and only if it contains no Mycielski-Grötzsch graph. This generalizes the main result of Deng and Chang [Graphs Combin. (2025) 41: 63]. |
| title | Structure, Perfect Divisibility and Coloring of ($P_2\cup P_4, C_3$)-Free Graphs |
| topic | Combinatorics 05C15, 05C75 |
| url | https://arxiv.org/abs/2509.14135 |