On minimal nonperfectly divisible fork-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_ | 1866913802416553984 |
|---|---|
| author | Xu, Baogang Zhuang, Miaoxia |
| author_facet | Xu, Baogang Zhuang, Miaoxia |
| contents | A fork is a graph obtained from $K_{1,3}$ (usually called claw) by subdividing an edge once. A graph is perfectly divisible if for each of its induced subgraph $H$, $V(H)$ can be partitioned into $A$ and $B$ such that $H[A]$ is perfect and $ω(H[B]) < ω(H)$. In this paper, we prove that the perfect divisibility of fork-free graphs is equivalent to that of claw-free graphs. We also prove that, for $F\in \{P_7, P_6\cup K_1\}$, each (fork, $F$)-free graph $G$ is perfectly divisible and hence $χ(G)\leq \binom{ω(G)+1}{2}$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2504_14863 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | On minimal nonperfectly divisible fork-free graphs Xu, Baogang Zhuang, Miaoxia Combinatorics A fork is a graph obtained from $K_{1,3}$ (usually called claw) by subdividing an edge once. A graph is perfectly divisible if for each of its induced subgraph $H$, $V(H)$ can be partitioned into $A$ and $B$ such that $H[A]$ is perfect and $ω(H[B]) < ω(H)$. In this paper, we prove that the perfect divisibility of fork-free graphs is equivalent to that of claw-free graphs. We also prove that, for $F\in \{P_7, P_6\cup K_1\}$, each (fork, $F$)-free graph $G$ is perfectly divisible and hence $χ(G)\leq \binom{ω(G)+1}{2}$. |
| title | On minimal nonperfectly divisible fork-free graphs |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2504.14863 |