no. 14 · Friday 13 November 2026
Perfect weight divisibility of (fork, co-fork$\cup K_1$)-free graphs
Abstract
A {\em fork} is a graph obtained from $K_{1,3}$ (usually called {\em claw}) by subdividing an edge once, an {\em co-fork} 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 subgraphs $H$, $V (H)$ can be partitioned into $A$ and $B$ such that $H[A]$ is perfect and $ω(H[B]) < ω(H)$. A graph is perfectly weight divisible if the same condition holds for any positive integer weights on its vertices, using the maximum weight of a clique instead of the clique number. Sivaraman proposed the conjecture that every fork-free graph is perfectly divisible in a paper by Karthick {\em et al.} [Electron. J. Comb. 29 (2022), P3.19.]. In the same paper, they proved that every ((\text{fork},\text{co-cricket}))-free graph is either claw-free or perfectly divisible. In this paper, we show that every (fork, co-fork$\cup K_1$)-free graph is perfectly weight divisible, and hence perfectly divisible. This improves some results of Karthick {\em et al.}.
- fields
- Combinatorics