Karthick–Kishore–Sahu conjecture on perfect divisibility of fork-free graphs

About 3 years old · traced to

A graph is perfectly divisible if, for every induced subgraph HH, its vertex set can be partitioned into AA and BB such that H[A]H[A] is perfect and ω(H[B])<ω(H)\omega(H[B])<\omega(H). A fork is obtained from the claw K1,3K_{1,3} 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.