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

About 1 year old · traced to

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.

References

Primary source

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

Progress summary

Never refreshed

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

Solutions 0

No solutions have been posted yet.