Karthick et al.'s perfect divisibility conjecture for fork-free graphs
Karthick et al.'s perfect divisibility conjecture for fork-free graphs
A graph is fork-free if it has no induced subgraph isomorphic to the graph obtained from by subdividing one edge once. A graph is perfectly divisible if, for each induced subgraph of , there is a partition such that is perfect and . 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
Sign in to submit a solution.
No solutions have been posted yet.