Every fork-free graph is perfectly weight divisible, confirming Sivaraman's conjecture and yielding chi(G) at most binomial(omega(G)+1,2) for every fork-free graph.
On minimal nonperfectly divisible fork-free graphs
1 Pith paper cite this work. Polarity classification is still indexing.
1
Pith paper citing it
abstract
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 $\omega(H[B]) < \omega(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 $\chi(G)\leq \binom{\omega(G)+1}{2}$.
citation-role summary
background 1
citation-polarity summary
fields
math.CO 1years
2026 1verdicts
CONDITIONAL 1roles
background 1polarities
unclear 1representative citing papers
citing papers explorer
-
Every fork-free graph is perfectly weight divisible
Every fork-free graph is perfectly weight divisible, confirming Sivaraman's conjecture and yielding chi(G) at most binomial(omega(G)+1,2) for every fork-free graph.