Perfect Divisibility and Coloring of Some Bull-Free Graphs
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866917365163229184 |
|---|---|
| author | Chen, Ran Wu, Di Yu, Junran Zhang, Xiaowen |
| author_facet | Chen, Ran Wu, Di Yu, Junran Zhang, Xiaowen |
| contents | 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, a {\em fork } is a graph obtained from $K_{1,3}$ by subdividing an edge once, and an {\em odd torch} is a graph obtained from an odd hole by adding an edge $xy$ such that $x$ is non-adjacent to any vertex on the odd hole and the set of neighbors of $y$ on the odd hole is a stable set.
Chudnovsky and Sivaraman [J. Graph Theory 90 (2019) 54-60] proved that every (odd hole, bull)-free graph and every ($P_5$, bull)-free graph are perfectly divisible. Karthick {\em et al.} [The Electron. J. of Combin. 29 (2022) P3.19.] proved that every (fork, bull)-free graph is perfectly divisible. Chen and Xu [Discrete Appl. Math. 372 (2025) 298-307.] proved that every ($P_7,C_5$, bull)-free graph is perfectly divisible. Let $H\in$\{\{odd~torch\}, $\{P_8,C_5\}\}$. In this paper, we prove that every ($H$, bull)-free graph is perfectly divisible. We also prove that a ($P_6$, bull)-free graph is perfectly divisible if and only if it contains no Mycielski-Grötzsch graph as an induced subgraph. As corollaries, these graphs are $\binom{ω+1}{2}$-colorable. Notice that every odd torch contains an odd hole, an induced $P_5$, and an induced fork. Therefore, our results generalize their findings. Moreover, we prove that every ($P_6$, bull)-free graph $G$ satisfies $χ(G)\leqω(G)^7$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_18856 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Perfect Divisibility and Coloring of Some Bull-Free Graphs Chen, Ran Wu, Di Yu, Junran Zhang, Xiaowen Combinatorics 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, a {\em fork } is a graph obtained from $K_{1,3}$ by subdividing an edge once, and an {\em odd torch} is a graph obtained from an odd hole by adding an edge $xy$ such that $x$ is non-adjacent to any vertex on the odd hole and the set of neighbors of $y$ on the odd hole is a stable set. Chudnovsky and Sivaraman [J. Graph Theory 90 (2019) 54-60] proved that every (odd hole, bull)-free graph and every ($P_5$, bull)-free graph are perfectly divisible. Karthick {\em et al.} [The Electron. J. of Combin. 29 (2022) P3.19.] proved that every (fork, bull)-free graph is perfectly divisible. Chen and Xu [Discrete Appl. Math. 372 (2025) 298-307.] proved that every ($P_7,C_5$, bull)-free graph is perfectly divisible. Let $H\in$\{\{odd~torch\}, $\{P_8,C_5\}\}$. In this paper, we prove that every ($H$, bull)-free graph is perfectly divisible. We also prove that a ($P_6$, bull)-free graph is perfectly divisible if and only if it contains no Mycielski-Grötzsch graph as an induced subgraph. As corollaries, these graphs are $\binom{ω+1}{2}$-colorable. Notice that every odd torch contains an odd hole, an induced $P_5$, and an induced fork. Therefore, our results generalize their findings. Moreover, we prove that every ($P_6$, bull)-free graph $G$ satisfies $χ(G)\leqω(G)^7$. |
| title | Perfect Divisibility and Coloring of Some Bull-Free Graphs |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2509.18856 |