Karthick et al.'s perfect divisibility conjecture for fork-free graphs

From papers

A graph GG is fork-free if it has no induced subgraph isomorphic to the graph obtained from K1,3K_{1,3} by subdividing one edge once. A graph is perfectly divisible if, for each induced subgraph HH of GG, there is a partition V(H)=A˙BV(H)=A\mathbin{\dot\cup}B such that H[A]H[A] is perfect and ω(H[B])<ω(H)\omega(H[B])<\omega(H). Karthick et al.'s conjecture. The class of fork-free graphs is perfectly divisible. Perfect divisibility provides a structural route to controlling the chromatic number of hereditary graph classes. The paper states this conjecture as previously proposed by Karthick et al.; no resolution is given in the supplied text.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

Ran Chen, Baogang Xu and Miaoxia Zhuang, “Perfect divisibility of (fork, antiforkK_1)-free graphs”, arXiv:2505.04429 (2025).

Solutions 0

No solutions have been posted yet.