Converse bounds for perfect divisibility of graphs

Perfect divisibility implies χ(H)≤ω(H)(ω(H)+1)/2 for every induced subgraph H. Does this hereditary chromatic bound conversely force the graph to be perfectly divisible?

Why it matters and what counts as progress

Why it matters: A converse would characterize a structural graph property using a numerical coloring bound.

What counts as progress: A proof of the converse or a graph satisfying the bound on every induced subgraph while failing perfect divisibility.

How the problem developed

2019 · Partial result [1]
Maria Chudnovsky and Vaidy Sivaraman Established the quadratic chromatic bound implied by perfect divisibility, giving a natural candidate converse.
14 Aug 2026 · Counterexample [1]
Zhiyu Wang and Weihao Xia Showed that the converse fails: every induced subgraph of the Paley graph P(17) meets the quadratic bound, although P(17) is not perfectly divisible.