Perfect divisions in ($P_2 \cup P_4$, bull)-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_ | 1866908483367993344 |
|---|---|
| author | Chen, Lizhong Wang, Hongyang |
| author_facet | Chen, Lizhong Wang, Hongyang |
| contents | A graph $G$ has a perfect division if its vertex set can be partitioned into two sets $A$, $B$ such that $G[A]$ is perfect and $ω(G[B]) < ω(G)$. We call $G$ perfectly divisible if every induced subgraph of $G$ admits a perfect division. We prove that every ($P_2 \cup P_4$, bull)-free graph $G$ with $ω(G) \geq 3$ has a perfect division if $G$ contains no homogeneous set. The clique-number condition is tight: a counterexample exists for $ω(G) = 2$. Additionally, we present a short proof of the perfect divisibility of ($P_5$, bull)-free graphs, originally established by Chudnovsky and Sivaraman [J. Graph Theory 90 (2019), 54-60.]. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2507_18506 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Perfect divisions in ($P_2 \cup P_4$, bull)-free graphs Chen, Lizhong Wang, Hongyang Combinatorics 05C15, 05C17, 05C69 A graph $G$ has a perfect division if its vertex set can be partitioned into two sets $A$, $B$ such that $G[A]$ is perfect and $ω(G[B]) < ω(G)$. We call $G$ perfectly divisible if every induced subgraph of $G$ admits a perfect division. We prove that every ($P_2 \cup P_4$, bull)-free graph $G$ with $ω(G) \geq 3$ has a perfect division if $G$ contains no homogeneous set. The clique-number condition is tight: a counterexample exists for $ω(G) = 2$. Additionally, we present a short proof of the perfect divisibility of ($P_5$, bull)-free graphs, originally established by Chudnovsky and Sivaraman [J. Graph Theory 90 (2019), 54-60.]. |
| title | Perfect divisions in ($P_2 \cup P_4$, bull)-free graphs |
| topic | Combinatorics 05C15, 05C17, 05C69 |
| url | https://arxiv.org/abs/2507.18506 |