A graph is \emph{perfectly weight divisible} if, for every positive integral weight function on and every induced subgraph of with at least one edge, the vertex set can be partitioned into two sets and such that is perfect and the maximum weight of a clique in is smaller than the maximum weight of a clique in . Perfect divisibility and its weighted form provide a natural approach to polynomial -boundedness. A \emph{fork}, also known as a \emph{chair}, is the graph obtained from a claw by subdividing one of its edges once. In this paper, we prove that every fork-free graph is perfectly weight divisible. As a consequence, we confirm a conjecture of Sivaraman that every fork-free graph is perfectly divisible.

生成讲解博客的中文版本

生成AI智能校验的中文版本