← All problems

Chudnovsky–Seymour precolouring-extension conjecture

For every claw-free perfect graph GG, every clique SS consisting of simplicial vertices, every integer k≥χ(G)k\geq\chi(G), every proper precoloring φ:S→{1,…,k}\varphi:S\to\{1,\ldots,k\} extends to a proper coloring ff of GG such that f(s)=φ(s)f(s)=\varphi(s) for all s∈Ss\in S and f(v)∈L(v)f(v)\in L(v) for every v∈V(G)∖Sv\in V(G)\setminus S, for every list assignment LL satisfying ∣L(v)∣≥k|L(v)|\geq k.

References

Source: arXiv

Progress summary

Refreshed
Open · solution reported

An unrefereed preprint claims to settle the conjecture, but no independent mathematical assessment was found.

The conjecture asserts that every proper precolouring of a simplicial clique extends from lists of size at least the graph's chromatic number, implying chromatic-choosability for claw-free perfect graphs. A recent survey still describes the corresponding chromatic-choosability conjecture as open.

Unrefereed preprint claim (date not stated)

Suchismita Mishra, Narayanan Narayanan, and Umesh Shankar claim that every proper precolouring of a simplicial clique extends from lists of size at least the chromatic number. If correct, this proves the Chudnovsky–Seymour conjecture and includes all perfect line graphs; the claim is unverified.

Current status (as of November 2026): The conjecture is claimed solved by an unrefereed preprint, but independent verification is absent and the result remains unverified.

Sources

Solutions 0

No solutions have been posted yet.