Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2505.04429 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866918012572925952 |
|---|---|
| author | Chen, Ran Xu, Baogang Zhuang, Miaoxia |
| author_facet | Chen, Ran Xu, Baogang Zhuang, Miaoxia |
| contents | A {\em fork} is a graph obtained from $K_{1,3}$ (usually called {\em claw}) by subdividing an edge once, an {\em antifork} is the complement graph of a fork, and a {\em co-cricket} is a union of $K_1$ and $K_4-e$. 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)$. Karthick {\em et al.} [Electron. J. Comb. 28 (2021), P2.20.] conjectured that fork-free graphs are perfectly divisible, and they proved that each (fork, co-cricket)-free graph is either claw-free or perfectly divisible. In this paper, we show that every (fork, {\em antifork}$\cup K_1$)-free graph is perfectly divisible. This improves some results of Karthick {\em et al.}. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2505_04429 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Perfect divisibility of (fork, antifork$\cup K_1$)-free graphs Chen, Ran Xu, Baogang Zhuang, Miaoxia Combinatorics A {\em fork} is a graph obtained from $K_{1,3}$ (usually called {\em claw}) by subdividing an edge once, an {\em antifork} is the complement graph of a fork, and a {\em co-cricket} is a union of $K_1$ and $K_4-e$. 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)$. Karthick {\em et al.} [Electron. J. Comb. 28 (2021), P2.20.] conjectured that fork-free graphs are perfectly divisible, and they proved that each (fork, co-cricket)-free graph is either claw-free or perfectly divisible. In this paper, we show that every (fork, {\em antifork}$\cup K_1$)-free graph is perfectly divisible. This improves some results of Karthick {\em et al.}. |
| title | Perfect divisibility of (fork, antifork$\cup K_1$)-free graphs |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2505.04429 |