Karthick–Kishore–Sahu conjecture on perfect divisibility of fork-free graphs
A graph is perfectly divisible if, for every induced subgraph , its vertex set can be partitioned into and such that is perfect and . A fork is obtained from the claw by subdividing one edge once. Karthick–Kishore–Sahu conjecture. The class of fork-free graphs is perfectly divisible. Perfect divisibility yields a quadratic upper bound on chromatic number in terms of clique number. The parser supplies no resolution evidence for this conjecture, so its status is left open.
References
Primary source
Di Wu and Baogang Xu, “Coloring_of_some_crown-free_graphs”, arXiv:2307.11946 (2023).
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.